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

网络流

图论

一、基本内容

>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

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