[Water]线性规划与网络流

【线性规划与网络流】(自己没解决的模型留念)

二分图算法

Hungary

KM

最大流算法

Dinic

SAP(充分优化)

费用流算法

spfa流

dijkstra流(spfa重标号)

zkw流

消圈算法

线性规划

单纯形法

对偶原理

分数规划

分数规划

[poj2728]
@最优比例生成树,每条边有费用和长度,求总费用比上总长度比值最小的生成树。二分比值mid,每次len=cost-mid*dis,直接求最小生成树,根据总长更改下上界。@
[最大密度子图]
@
无向图中求出一个子图,使得边权和与点权和的比值最大。
题意即是求,其中为包含中所有边的端点的最小集合。
设最优答案为
,显然,且函数单调递减。
那么转化为求出.
显然选出一条边后其两个端点必然选择,利用最大权闭合图模型,将边视作点,且分别加权,求出闭合图最大权,记为函数的值。
@
[bzoj3232圈地游戏]
@
这道分数规划出奇得不是最大权闭合图模型。。。
只需要最小割就行了。
算出将集合划分开来的最小付出的代价,利用最小割求解。
启示良多。。。

利用ISAP,rank8了。
@

网络流建模

二分图匹配建模

[棋盘放置]
棋盘上有若干个障碍,在非障碍格子处放置最多的棋子使得任意在同一直线上的两个棋子中间被障碍物隔开。
@
每一行和每一列的的每一个连通块作为点,交点作为边,求出最大匹配。
@
[二分图多重匹配]
@
直接最大流水过。。。
@

最小割建模

[最大权闭合图]
从最小割角度考虑建模正确性。
由于势必要按照点是否在闭合图中将所有点划分为两部分。
一个点划分到S集合表示其在选中的闭合图中。
若有有向边,那么在流网络中连接边,保证在一个集合中。
若点权值,连接
若点权值,连接
考虑求出的最小边权割集,显然是简单割,flow=未选中的正权值点权值和-选中的负权值点权值和。
那么容易知道答案ans=所有的正权值点权值和-flow=选中的正权值点权值和+选中的负权值点权值和。
显然所有的正权值点权值和为定值,flow又为最小割,那么答案是正确的。
[二分图最小点权覆盖集]
@
最小点覆盖等于最大匹配的都滚粗。。。
需要满足的条件是:



在新图上求出最小割。
考虑每一条路径,考虑边割集,那么必然有
我们容易发现这样的一个边割集必然对应着一个之前的集合,而且最小割算法保证了其最优性,那么就这样完了。
输出方案显然BFS.
@
[二分图最大点权独立集]
@
点覆盖集的补集是一个点独立集。
证明:假设其补集不是点独立集,那么存在边,使得均在集合中,那么就是说点覆盖集中均不在集合中,那么在点覆盖集中边未被覆盖,产生矛盾。证毕。
最小点权覆盖集的补集是最大点权独立集。
证明:权值和恒定,显然成立。
@
[能量魔方]
@
首先是二分图,而且有一些被强制划分集合,然而求的是最大的相邻的不在一个集合的数目。
如果像原来一样求出的最小割表示的是最少的不在一个集合的数目,显然不对。
那么由ans=总集-(最小的)相邻的在一个集合的数目,转化一下:
令S集表示划分到X集的P和划分到Y集的N,T集表示划分到X集的N和划分到Y集的P.
那么我们惊奇的发现,割掉的边就是两个集合X,Y中颜色相同的最小对数!
那么答案=总边数-最大流。
注意连双向边。
@
[JDFZOJ1034]
已知一些球队的胜负情况,以及球队之间的剩余比赛数目,求给定球队是否能够严格比其他的所有球队分数高。
对于一场比赛:胜+2,负+0,平+1.
@
首先令给定球队赢得剩下的所有比赛,然后让剩下的比赛分配流量。
给剩下的球队x流量限制finalpoint[0]-nowpoint[x]-1,如果所有的比赛全部满流则可以。
@

最大流&费用流建模

[NOI2012]美食节
@
动态加边加点的最小费用流。
即:处理完第i位厨师倒数第j道菜,再处理第i位厨师倒数第j+1道菜。。。
每次加入一个点,n条边。
@
[Poj3680]最大权区间覆盖,使每一个实数被覆盖不超过k次。
@
自己想到了建模,居然觉得不对。。。
@
[CQOI2014]危桥
@
s-a1,t-a2,s-b1,t-b2;s-a1,t-a2,s-b2,t-b1均满流则满足条件
证明有时间再说。。
@

网络流&线性规划

/参考课件/
线性规划与网络流-曹钦翔
网络流-lyy
线性规划的对偶理论

comments powered by Disqus