Day5 网络流 费用流

湖南师大2018.1.6

P5

S、T的流量是不平衡的，由T向S连边，使S、T的流量平衡，转成无源汇

路径覆盖

二分图匹配做法：
　　DAG最小路径覆盖：n-最大匹配数。
　　DAG最小链覆盖：Floyd预处理每个点i能到达的所有点，由i向所有这些点连边。但Floyd复杂度有点高。
上下界网络流做法：
　　最小路径覆盖：每个点拆点，限制上下界[1,1]，不同点间边的流量为1；S向每个点连INF的边，每个点向T连INF的边。
　　最小链覆盖：将每个点的上下界改为

Dilworth定理：
对于DAG，$x可达y$ 是一个偏序关系。
对于非DAG不是。
ps：偏序关系
设R是集合A上的一个二元关系，若R满足：1. 自反性：对 $\bigvee x\in A$，有$xRx$
2. 反对称性：对 $\bigvee x,y\in A$，若$xRy$，且$yRx$，则 $x=y$。
3. 传递性：对 $\bigvee x,y,z\in A$，若$xRy$，且$yRz$，则$xRz$。
则称R为A上的偏序关系，通常记作$\preccurlyeq$。注意这里的$\preccurlyeq$不必是指一般意义上的小于或等于。
若有$x\preccurlyeq y$，我们也说x排在y前面（$x\ precedes\ y$）。

P44

　　考虑所有可能状态，把状态连起来

费用流

P63

正确性：因为匹配一定不相交

P79 证明

唯一没有覆盖到的点就是链的终点，其出度为0，但红蓝点集合是两个图的匹配，所以里面的点出度都为1,，所以不需要考虑那个终点。

SPFA可以处理负边，zkw不能处理负边；
都不能处理负环。
有盈余量的情况下处理可行流：

先保证最优，逐渐令其可行。

p11

限制流量相等的情况，可以通过加一维费用解决。（由列向行连(INF,0)?）

P13

每个点可以向4个方向贡献1的度数，费用是不同的（0*1/1*3）。
-> 使每个点入度为1且费用最小

P47

志愿者工作是一个连续的区间，所以可以转化为费用流去做。
对等式差分
每个x,y变量恰好出现两次，所有等式左/右边相加都为0。
x:因为是一个区间
y:只出现在一个等式中
变量+1相当于是流量转移，如每当$x_1+1$，1'流量-1，3'+1

P54

线段树：一个点维护k个值，但合并复杂度为$O(k^2)$，...
写个暴力费用流，考虑每次增广在干什么

P59

用DP去模拟，f[i]表示从这个点出发走到某一个点，走到子树中的某个点最优，这个最小值。

ppt P5
这个怎么理解...求教qvq
刘昀
你说哪个方法
ljm
两个（
ljm
这是处理带上下界的负边/圈吗
刘昀
有没有上下界都可以
ljm
没有上下界的话超级源汇怎么建（
刘昀
实际上我们通过下界计算出每个点的盈余量，根据盈余量的正负建图
刘昀
而这个问题每个点实际上都有盈余量，于是直接根据正负建图就好了
hzw
下界是利用负权边算的吗
ljm
无上下界的呢
hzw
就是复权下界是容量？
刘昀
让负权边强制满流，这破坏了流量平衡的条件，类似下界的强制满流
刘昀
于是本质上和上下界网络流相同，都是建超级源汇满足流量平衡
hzw
如果没有可行流呢？
hzw
这样的话是不是理解成尽可能优先满负边
刘昀
是的
hzw
然后让从s到t的经过负权的增广都是退流？
刘昀
你会发现消负圈的算法必然存在可行流，因为实在不行你可以把负边都退流，这必然可行
刘昀
对，负权边全都转化成反向的正权边，每流过1单位流量都意味着退了负边
ljm
那么强制满流后建不建反向正权边
17:59:04
刘昀
建，它的流量表示反向边的退流量
18:20:42
ljm
最后再问下。。方法二是只求最大流吗qvq还是有什么办法继续求费用
hzw
最后一种方法ss- s t- tt也要连正无穷的边吗
刘昀
一次超级源点到超级汇点的最小费用最大流，它能同时保证原图取到最大流和最小费用
刘昀
ss和tt具体连向哪些点，根据盈余量的正负决定
18:26:39
hzw
就是第二种比如s-t 100 2 ，s-t 2 -2这种情况下光让负边强制满流超级源只有2的流出啊
18:53:52
刘昀

刘昀
这是你这个样例
刘昀
其中+∞也是一个大数y
刘昀
ans+=SS到TT的最小费用最大流的费用值
刘昀
最终$ans=-102*x+100*2+2*(-2)$，x前方的系数的相反数（102）表示最大流的值，剩余的部分表示最小费用的值