[关闭]
@xzyxzy 2018-06-24T17:07:26.000000Z 字数 8998 阅读 3016

网络流

图论


一、基本内容

>Dinic基本内容

SYC:http://www.cnblogs.com/SYCstudio/p/7260613.html
朴素DFS->局限性->反悔边->低效->分层图->当前弧优化->Dinic!

>费用流基本内容

本宝宝自己写:
1.在每一条边上有单位流量的费用,你要保证流量最大的前提,费用最小
2.算法由最朴素的算法该进,便是在BFS求增广路的时候以费用为关键字跑SPFA
3.看代码

>上下界网络流

留坑

>最长反链覆盖

留坑


二、题目

1、练基础

2、刷提高

3、网络流24题

不可做题:P2775 机器人路径规划问题 https://www.luogu.org/problemnew/show/P2775

4、考试题


三、做题经验

Part 1 易打错

1、当前弧优化的循环终点别弄错

  1. while(BFS())
  2. {
  3. for(int i=1;i<=cnt;i++)cur[i]=head[i];
  4. while(int tmp=DFS(S,INF))ans+=tmp;
  5. }
  1. for(int i=1;i<=点数;i++)cur[i]=head[i];

题目来源:试题库问题P2763

2、源点的deep一定要是1 不然跑不出来

  1. deep[S]=0;Q.push(S);
  1. deep[S]=1;Q.push(S);

3、跑最大费用最大流时,dis初值为-inf

  1. for(int i=0;i<=T;i++)dis[i]=-10000;
  1. for(int i=0;i<=T;i++)dis[i]=-1;

因为有-cost的边所以-1会出错
题目来源:分配问题P4014

4、最大流,费用流都可以跑环

最大流分层图可以跑环,费用流SPFA也可以


Part 2 技巧

1、拆点连边技巧

蜥蜴:https://www.luogu.org/problemnew/show/P2472
为了限制一个点的流量,将它拆成两个点并连边

有向边的时候一条边为w,cost,反过来为0,-cost
无向边正反都是w

2、记录匹配方案

满流的边便是匹配上了
P2763 试题库问题 https://www.zybuluo.com/mdeditor#980353
P2756 飞行员配对方案问题 https://daniu.luogu.org/problemnew/show/2756

3、某边改变时

并不需要重新建图
A、判断某条边(u->v)属不属于割集,那么在残余网络中u到达不了v
B、对于一条边扩容,那么在残余网络上找增广路就好了
C、减少一条边的容量,在残余网络中找是否有该容量的路,再分情况更新
例:团圆(考试题),看某一条边是不是必须要的,重新跑SPFA即可

4、最小割问题

最小割:
割是网络中定点的一个划分,它把网络中的所有顶点划分成两个顶点集合S和T,其中源点s∈S,汇点t∈T。记为CUT(S,T),满足条件的从S到T的最小的割

百度告诉我们,最小割等于最大流
但是求的是割点的时候呢,哈哈,死掉了吧————奶牛的电信
这些最小割真的哦心【你猜呀!】【你阅读了吗?】【死掉了吧~

5、有关术语

参考博客:https://www.cnblogs.com/jianglangcaijin/p/6035945.html

最小顶点覆盖
能覆盖所有的边的最少顶点数(或是最小点权和)

计算方法:最小顶点覆盖=最大匹配数

最大独立集
两两互不相邻的点组成的集合的最大点数(或是最大点权和)

计算方法:最大独立集=点总数-最小顶点覆盖
例题剖析——方格取数问题
和小行星有点类似,小行星是x,y,z要消掉一个使得消掉行星,便是S-x-y-z-T的流不存在,即求最小割,转化为最大流;此题把方格化为黑白点,便不存在 S->黑点->白点->T的流,顺次进行连边求最小割即最大流即可,注意边权
又用转化思想,化为黑白点后可以看做二分图,便成了最大独立集,为总点数-最小顶点覆盖(最大匹配/最小割)

最小路径覆盖
能覆盖所有点的最少边数(边权之和)
友链:http://blog.csdn.net/tramp_1/article/details/52742572

计算方法:二分图最小路径覆盖=一侧点数-最大匹配数
运用:常用来解决不重不漏经过图中所有点的问题,一般化u为u和u',对于边(u,v),link(u,v'),最大匹配数在网络流中就是最小割/最大流,看看这题
理解:最差每个点就是一条路径,每连一条边(一个匹配)就少一条路径,n-匹配数
ps:自己习惯于跑费用流,把点拆成上下两层后这样搞:
  link(S,u,1,0); link(S,u',1,1); link(u',T,1,0); link(u,v',1,0);

最大权闭合子图
给定一个有向图,从中选择一些点组成一个点集V。对于V中任意一个点,其后续节点都仍然在V中

计算方法:最大权=所有正点和-最小割
或者说是最大收益问题【模板1】【模板2】【模板3


Part 3 转化思想

1、最小割思想

很多情况下,对于网络中的每个点存在有两种状态,选或不选同意或反对等等
就将它们分成两个集合S,T表示两种对立的状态,而且点与点之间也有相互的关系
改变某点的状态需要一定代价,并因此连边。

举个例子
最大权闭合子图中,假设所有实验都选,获得收益,那么最终答案是总收益-总损失,损失表示买一个器材的代价或者放弃一个实验的损失
每个实验和器材存在有选或不选的关系,假设选为S,不选为T,那么把实验与S连边,器材与T连边后,损失成了图的最小割,最小割的割集一定由与S/T相连的边组成(中间为正无穷)。当实验不选的时候,相当于割掉其与S的边,造成其边流量的损失,计算到最小割里;当器材要选的时候,相当于割掉其与T的边,造成其边流量的代价买器材,计算到最小割里。

边容量
一般呢,哪两个点不可割就连inf,x连到S会产生w贡献那么连x到T,容量为w

2、上升序列思想

主要是这题,求某一长度的上升序列的个数,那么转化成最大流,DP求出转移后,每个点只能向该点转移到的点连边(并不是比它大就能连边),所以一条流经过的路径数就是上升序列的长度。


最大流模板

  1. //https://www.luogu.org/problemnew/show/3376
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<queue>
  7. using namespace std;
  8. const int MAXN=10010;
  9. const int MAXM=100010;
  10. int N,M,S,T,ans,deep[MAXN];
  11. int head[MAXN],cnt=1,cur[MAXN];
  12. struct edge{int next,to,w;}a[MAXM<<1];
  13. void link(int x,int y,int w){a[++cnt]=(edge){head[x],y,w};head[x]=cnt;}
  14. int read();
  15. queue<int>Q;
  16. int BFS()//分好层
  17. {
  18. memset(deep,0,sizeof(deep));
  19. deep[S]=1;Q.push(S);
  20. while(!Q.empty())
  21. {
  22. int now=Q.front();Q.pop();
  23. for(int i=head[now];i!=-1;i=a[i].next)
  24. if(!deep[a[i].to]&&a[i].w)
  25. {deep[a[i].to]=deep[now]+1;Q.push(a[i].to);}
  26. }//给每个深度编号
  27. return deep[T];
  28. }
  29. int DFS(int x,int flow)//在该层寻找所有增广路
  30. {
  31. if(x==T)return flow;//返回最大流
  32. for(int &i=cur[x];i!=-1;i=a[i].next)
  33. //&这个符号,表示i去到cur[x]的地址,那么首先i=cur[x]然后随着i的改变cur[x]跟着改变
  34. {
  35. if(!a[i].w||deep[a[i].to]!=deep[x]+1)continue;//要求有流且在下一层
  36. int tmp=DFS(a[i].to,min(a[i].w,flow));
  37. if(tmp){a[i].w-=tmp;a[i^1].w+=tmp;return tmp;}
  38. //记得加反悔边,return tmp表示找到一条流就退出,是单路增广
  39. }
  40. return 0;
  41. }
  42. int main()
  43. {
  44. //Part 1 输入建图
  45. N=read();M=read();
  46. S=read();T=read();
  47. memset(head,-1,sizeof(head));
  48. for(int i=1;i<=M;i++)
  49. {
  50. int x=read(),y=read(),w=read();
  51. link(x,y,w);link(y,x,0);//建边的时候要建立反悔边
  52. }
  53. //Part 2 逐层找增广路
  54. while(BFS())//走的到终点即存在增广路
  55. {
  56. for(int i=1;i<=N;i++)cur[i]=head[i];//当前弧优化
  57. while(int tmp=DFS(S,10000000))ans+=tmp;//加上增广的最大流
  58. }
  59. printf("%d\n",ans);
  60. return 0;
  61. }
  62. int read()
  63. {
  64. char ch=getchar();
  65. int h=0;
  66. while(ch>'9'||ch<'0')ch=getchar();
  67. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  68. return h;
  69. }
  70. /*
  71. 网络流Dinic
  72. 1.流程:
  73. A.输边建图(记得加上反悔边)
  74. B.分层跑增广路
  75. C.重复B直到从源点走不到汇点
  76. 2.理解:
  77. A.反悔边:详见SYC博客http://www.cnblogs.com/SYCstudio/p/7260613.html
  78. B.如何说明分层跑是对的或者说如何跑的:
  79. a.每一层跑完后,S一定会到不了T
  80. b.那么在deep[T]步走不到T,那么要走到T,必须加上之前连接同一层的两个点,deep[T]至少加1
  81. C.复杂度:
  82. 分层M,至少分N次,DFS一次是N,然后一次至少有一条边流满即剩余流量为0,视为删掉一条边
  83. 然后也许有M次所以复杂度为O(N*N*M)
  84. 然而实际上复杂度要小的多,这道题10000*10000*100000可是在0.05ms内跑过的
  85. D.当前弧优化:
  86. 每次分好层之后,对于点P,有流进P的边和从P流出的边
  87. 如果这条边流出满了,下次就不要搜这条边,用cur记录(没流满就return了)
  88. */

费用流模板

  1. //https://www.luogu.org/problemnew/show/P3381
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<queue>
  7. using namespace std;
  8. int read()
  9. {
  10. char ch=getchar();
  11. int h=0;
  12. while(ch>'9'||ch<'0')ch=getchar();
  13. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  14. return h;
  15. }
  16. const int MAXN=5001;
  17. int N,M,S,T,head[MAXN],cnt=1,anssum=0,anscost=0;
  18. struct edge{int next,to,w,cost;}a[MAXN*20];
  19. void link(int x,int y,int w,int cost)
  20. {
  21. a[++cnt]=(edge){head[x],y,w,cost};head[x]=cnt;
  22. a[++cnt]=(edge){head[y],x,0,-cost};head[y]=cnt;
  23. }
  24. queue<int>Q;
  25. int dis[MAXN],e[MAXN],pe[MAXN],px[MAXN];
  26. //pe[i]表示到达i点的那一条边的编号
  27. //px[i]表示到达i点的前驱节点编号
  28. bool SPFA()
  29. {
  30. memset(dis,63,sizeof(dis));
  31. dis[S]=0;Q.push(S);
  32. while(!Q.empty())
  33. {
  34. int x=Q.front();
  35. for(int i=head[x];i!=-1;i=a[i].next)
  36. {
  37. int R=a[i].to;
  38. if(!a[i].w||dis[R]<=dis[x]+a[i].cost)continue;
  39. dis[R]=dis[x]+a[i].cost;
  40. pe[R]=i;px[R]=x;
  41. if(!e[R]){e[R]=1;Q.push(R);}
  42. }
  43. e[x]=0;Q.pop();
  44. }
  45. return dis[T]<dis[0];
  46. //当不存在增广路时dis[T]=dis[0]
  47. }
  48. int main()
  49. {
  50. //init
  51. N=read();M=read();S=read();T=read();
  52. memset(head,-1,sizeof(head));
  53. for(int i=1;i<=M;i++)
  54. {
  55. int x=read(),y=read(),w=read(),cost=read();
  56. link(x,y,w,cost);
  57. }
  58. //work
  59. while(SPFA())//算出增广路上的流
  60. {
  61. int sum=1e9;
  62. for(int i=T;i!=S;i=px[i])
  63. sum=min(sum,a[pe[i]].w);
  64. anscost+=dis[T]*sum;//记录最小费用-流量×每条边单位流量费用之和
  65. anssum+=sum;//记录最大流
  66. for(int i=T;i!=S;i=px[i])
  67. a[pe[i]].w-=sum,a[pe[i]^1].w+=sum;//逐边减
  68. }
  69. printf("%d %d\n",anssum,anscost);
  70. return 0;
  71. }

参考文献:

SYC:http://www.cnblogs.com/SYCstudio/p/7260613.html

ZSY:https://www.luogu.org/blog/zhoushuyu/wang-lao-liu-zong-jie

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注