最大流/最小割
- 增量建图
- 最大权闭合子图
- 二分检验
- 最小割一定要找全矛盾关系，如文理分科 选文选理，同选文同选理矛盾
- 最大流的一个单位流量经过的点代表的是这个点的特征
- 最小割就是如果能从S到T，那么这条路就是非法的，如果单个点矛盾关系不是很多，可以建立每个点和所有矛盾关系之间的
- 先处理好局部的关系，再拓展到全局，如：employ人员雇佣 对于两点a,b之间存在 选a选b 减去$c_a,c_b$ 选a,b其中一个 减$E_{a,b}*2,c_a/c_b$,不选a,b减$E_{a,b}$
- 然后可以发现，如果不选i，那么所有的$E_{i,j}$都得不到，所以可以连边表示$sum_i$与$c_i$的取舍关系，发现只选一个还要多减，再连边$a->b,b->a$
- 这样如果两条与源点相连的边被割掉合法，两条与汇点割掉也合法，当只有一个割掉的时候，S与未选点之间还是有流量，流向所有的已选点，满足题意。
1 inline bool bfs() 2 { 3 memset(d,0,sizeof d); 4 d[q[h=t=0]=S]=1;hd[S]=head[S]; 5 while(h<=t) 6 { 7 int x=q[h++]; 8 for(int i=head[x],y;i;i=nxt[i]) 9 { 10 if(!val[i]||d[y=to[i]]) continue; 11 d[q[++t]=y]=d[x]+1;hd[y]=head[y]; 12 if(y==T) return 1; 13 } 14 } 15 return 0; 16 } 17 int dfs(int x,int f) 18 { 19 if(!f||x==T) return f; 20 int las=f; 21 for(int &i=hd[x],y;i;i=nxt[i]) 22 { 23 if(!val[i]||d[y=to[i]]!=d[x]+1) continue; 24 int t=dfs(y,min(las,val[i])); 25 if(t) val[i]-=t,val[i^1]+=t,las-=t; 26 else d[y]=0; 27 if(!las) return f; 28 } 29 return f-las; 30 }
费用流
- 费用流还是满足一个单位流量的特征
- 一般最大流来保证满足题设，费用是最优化花费
- 灵活转化题意。
- 有些题要求每个点均遍历一遍，可以转化为每个点的入度出度均为1，可以想到拆点，把一个点拆成入点和出点，限流最大流量为n，直接最小费用最大流
- 有些题要求一定要跑满，可以把你想跑满的边的边权设为-inf，最后再加上，这样保证跑想跑的边一定比其他的费用小，可以说是skyh对网络流的深刻理解。
- 对于有一些问题子集分化不明显，考虑利用条件把其转化为二分图。如：数字配对，千钧一发
- 有一些简单的优化 如：动态开点，不要思维僵化只想增量枚举！！！费用流不能跑在残量网络上跑。
- 一类套路：配对问题考虑利用特殊性质转化为二分图
- 网格图优先想黑白染色！！！！
上下界网络流
- 其实就是想办法把下届的条件去掉
- 无源汇可行流是基础，先构造一个不满足流量守恒，跑满下届，再跑一个附加流，建虚拟源汇点，调整每个点的出入流量，跑就完了。
- 对于有源汇的，因为S和T不满足流量守恒，建一条从T到S的INF边就好了
- 最大流和最小流都是通过在残量网络上跑来实现的。
- 如果虚拟源汇点跑满了，说明存在合法解，此时的残量网络是一个合法解，但是不一定是我们想要的。