发现好久没来写总结了
做了一星期+的网络流 还讲了两节课 是时候写个总结了
分类：
最大流： 用sap做 如果是平面图 可以对偶转换再求最短路
最小割： 求法和最大流一样 方案可以用bfs求
费用流： 用spfa做 如果时间过不了可以用zkw费用流（虽然我还不会- -）
上下界：
建立虚拟源、汇 求虚拟源汇最大流 若满流则有解
最大流： 先按虚拟源汇跑最大流 再按原本源汇跑最大流
最小流： 先不连原本汇到源的无穷大边 按虚拟源汇跑最大流 再连原本汇到源的边 再跑一次最大流
费用最大\最小流： 把上下界最大\最小流的sap改成spfa即可
应用：
减少点的个数：
看《网络流建模汇总》提到 如果想不出比较高效的建图方法 可以先建一张最简单的图 再按一下规律缩点
1.如果几个结点的流量的来源完全相同 则可以把它们合并成一个
2.如果几个结点的流量的去向完全相同 则可以把它们合并成一个
3.如果从点u到点v有一条容量为∞的边 并且点v除了点u以外没 有别的流量来源 则可以把这两个结点合并成一个
题目：poj 1149
入度&出度：
一些限定入度出度大小 并且有一些双向边让你定向的题目
可以先随便定一个方向再把源连到入度大于限定额额度的点 把入度小于限定额额度的点连到汇 容量为|入度-限定入度|
题目：poj 1637、poj 2699
拆点：
在限制点容量的题目 可以将一个点拆成两个点 将点转换为边 即可限制点容量
一些有层次性的题目 如不同时间点之间联通性不同 可以把一个点拆成若干点
题目：很多题目都要拆点- - 就不列举了
边转换为点：
如果一条边是有决策性的 如两点二选一 可以把这条边转换为点
再向它连的点各连一条边 只给这个点1的流量 就能实现二选一的效果
如果必须选某一个 可以不连另外一条边
题目：woj 1124
特殊的线性规划：
求不等式组的解 其中不等式中的变量都是连续的 把不等式左边加上一个yi 使不等式变等式
再把相邻的等式做差 这样每个变量在所有的等式中就只会正负各出现一次
把-xi连向xi 常数根据正负连到源或汇 跑最大流 剩余网络边权即为变量值
SAP代码：
传说中神一般的实现，会背即可
1 int sap(int t,int delta){ 2 if (t==T) return delta; 3 int mindis=nodes,sum=0; 4 for (int i=son[t];i;i=line[i].next){ 5 if (line[i].f>0 && dis[line[i].key]+1==dis[t]){ 6 int save=sap(line[i].key,min(line[i].f,delta-sum)); 7 sum+=save; 8 line[i].f-=save; 9 line[line[i].op].f+=save; 10 if (dis[S]>=nodes || sum==delta) return sum; 11 } 12 if (line[i].f>0) mindis=min(mindis,dis[line[i].key]); 13 } 14 if (sum==0){ 15 if (!--cnt[dis[t]]) dis[S]=nodes; 16 else ++cnt[dis[t]=mindis+1]; 17 } 18 return sum; 19 } 20 int main(){ 21 while (dis[S]<nodes) ans+=sap(S,INF); 22 } View Code
费用流代码：
1 bool spfa(){ 2 memset(dis,0x3f,sizeof(dis)); 3 memset(bo,0,sizeof(bo)); 4 dis[S0]=0; 5 que.push(S0); 6 while (!que.empty()){ 7 int now=que.front(); 8 que.pop(); 9 bo[now]=0; 10 for (int i=son[now];i;i=line[i].next) 11 if (line[i].f){ 12 int ne=line[i].data; 13 if (dis[ne]>dis[now]+line[i].cost){ 14 dis[ne]=dis[now]+line[i].cost; 15 from[ne]=now; 16 fl[ne]=i; 17 if (!bo[ne]){ 18 bo[ne]=1; 19 que.push(ne); 20 } 21 } 22 } 23 } 24 return dis[T0]<0x3f3f3f3f; 25 } 26 void work(){ 27 int minf=INF; 28 for (int i=T0;i!=S0;i=from[i]) 29 minf=min(minf,line[fl[i]].f); 30 for (int i=T0;i!=S0;i=from[i]){ 31 int now=fl[i]; 32 line[now].f-=minf; 33 line[line[now].op].f+=minf; 34 ans+=line[now].cost*minf; 35 } 36 } 37 int main(){ 38 while (spfa()) work(); 39 } View Code
上下界最大流代码（主程序）：
1 for (int i=1;i<=m;i++){ 2 scanf("%d%d%d%d",&x,&y,&b,&c); 3 out[x]+=b; 4 in[y]+=b; 5 addline(x,y,c-b); 6 } 7 for (int i=1;i<=n;i++){ 8 int m=in[i]-out[i]; 9 if (m>0) addline(S0,i,m); 10 if (m<0) addline(i,T0,-m); 11 } 12 SS=S0,TT=T0; 13 addline(T,S,INF); 14 while (dis[SS]<nodes) sap(SS,INF); 15 memset(dis,0,sizeof(dis)); 16 memset(cnt,0,sizeof(cnt)); 17 cnt[0]=nodes; 18 SS=S,TT=T; 19 while (dis[SS]<nodes) sap(SS,INF); View Code
上下界最小流代码（主程序）：
1 for (int i=1;i<=m;i++){ 2 scanf("%d%d%d%d",&x,&y,&b,&c); 3 out[x]+=b; 4 in[y]+=b; 5 addline(x,y,c-b); 6 } 7 for (int i=1;i<=n;i++){ 8 int m=in[i]-out[i]; 9 if (m>0) addline(S0,i,m); 10 if (m<0) addline(i,T0,m); 11 } 12 SS=S0,TT=T0; 13 while (dis[SS]<nodes) sap(SS,INF); 14 addline(T,S,INF); 15 memset(dis,0,sizeof(dis)); 16 memset(cnt,0,sizeof(cnt)); 17 cnt[0]=nodes; 18 while (dis[SS]<nodes) sap(SS,INF); View Code
转载于:https://www.cnblogs.com/g-word/p/3479188.html
