网络流入门—用于最大流的Dinic算法

时间：2022-05-06 04:29:35

网络流入门—用于最大流的Dinic算法

Posted 2011年05月2日 by comzyh

“网络流博大精深”—sideman语

网络流入门—用于最大流的Dinic算法一个基本的网络流问题
感谢WHD的大力支持

最早知道网络流的内容便是最大流问题，最大流问题很好理解：

解释一定要通俗!

如右图所示,有一个管道系统,节点{1,2,3,4},有向管道{A,B,C,D,E},即有向图一张. [1]是源点,有无限的水量,[4]是汇点,管道容量如图所示.试问[4]点最大可接收的水的流量?

这便是简单的最大流问题,显然[4]点的最大流量为50

死理性派请注意:流量是单位时间内的,总可以了吧!

然而对于复杂图的最大流方法是什么呢,有EK,Dinic,SAP,etc.下面介绍Dinic算法(看代码的直接点这)

Dinic 算法

Dinic算法的基本思路:
  1. 根据残量网络计算层次图。
  2. 在层次图中使用DFS进行增广直到不存在增广路
  3. 重复以上步骤直到无法增广

引自NOCOW,相当简单是吧…

小贴士:

一般情况下在Dinic算法中,我们只记录某一边的剩余流量.

  • 残量网络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量网络,
  • 层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3})
  • DFS:这个就不用说了吧…
  • 增广  :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差)
  • 增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?)
  • 剩余流量:当一条边被增广之后(即它是增广路的一部分,或者说增广路通过这条边),这条边还能通过的流量.
  • 反向弧:我们在Dinic算法中,对于一条有向边,我们需要建立另一条反向边(弧),当正向(输入数据)边剩余流量减少I时,反向弧剩余流量增加I
Comzyh的较详细解释(流程) :


Dinic动画演示
  1. 用BFS建立分层图  注意:分层图是以当前图为基础建立的,所以要重复建立分层图
  2. 用DFS的方法寻找一条由源点到汇点的路径,获得这条路径的流量I 根据这条路径修改整个图,将所经之处正向边流量减少I,反向边流量增加I,注意I是非负数
  3. 重复步骤2,直到DFS找不到新的路径时,重复步骤1

注意(可以无视):

  • Dinic(其实其他的好多)算法中寻找到增广路后要将反向边增加I
  • Dinic中DFS时只在分层图中DFS，意思是说DFS的下一个节点的Dis(距源点的距离)要比自己的Dis大1,例如在图1中第一个次DFS中,1->2->4 这条路径是不合法的,因为Dis[2]=1;Dis[4]=1;
  • 步骤2中“获得这条路径的流量I “实现:DFS函数有参量low,代表从源点到现在最窄的(剩余流量最小)的边的剩余流量,当DFS到汇点是,Low便是我们要的流量I
对于反向弧(反向边)的理解:

这一段不理解也不是不可以,对于会写算法没什么帮助,如果你着急,直接无视即可.
先举一个例子(如右图):

网络流入门—用于最大流的Dinic算法必须使用反向弧的流网络

在这幅图中我们首先要增广1->2->4->6,这时可以获得一个容量为2的流,但是如果不建立4->2反向弧的话,则无法进一步增广,最终答案为2,显然是不对的,然而如果建立了反向弧4->2,则第二次能进行1->3->4->2->5->6的增广,最大流为3.

Comzyh对反向弧的理解可以说是”偷梁换柱“,请仔细阅读:在上面的例子中,我们可以看出,最终结果是1->2->5->6和1->2->4->6和1->3->4->6.当增广完1->2->4->5(代号A)后,在增广1->3->4->2->5->6(代号B),相当于将经过节点2的A流从中截流1(总共是2)走2->5>6,而不走2->4>6了,同时B流也从节点4截流出1(总共是1)走4->6而不是4->2->5->6,相当于AB流做加法.

简单的说反向弧为今后提供反悔的机会,让前面不走这条路而走别的路.

Alwa同学非要我给他的文章加一个链接,大家可以看看他的文章: 有关网络流中的反向弧和增广路

Dinic算法的程序实现

最大流算法一直有一个入门经典题:POJ 1273 或者是UCACO 4_2_1 来自NOCOW(中文) 这两个是同一个题

给出这道题的代码：

[cpp] view plain copy  
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <cstdlib>  
  4. #include <iostream>  
  5. #define min(x,y) ((x<y)?(x):(y))  
  6. using namespace std;  
  7. const int MAX=0x5fffffff;//  
  8. int tab[250][250];//邻接矩阵   
  9. int dis[250];//距源点距离,分层图   
  10. int q[2000],h,r;//BFS队列 ,首,尾   
  11. int N,M,ANS;//N:点数;M,边数   
  12. int BFS()  
  13. {  
  14.      int i,j;  
  15.      memset(dis,0xff,sizeof(dis));//以-1填充   
  16.      dis[1]=0;  
  17.      h=0;r=1;  
  18.      q[1]=1;  
  19.      while (h<r)  
  20.      {  
  21.            j=q[++h];  
  22.            for (i=1;i<=N;i++)  
  23.                if (dis[i]<0 && tab[j][i]>0)  
  24.                {  
  25.                   dis[i]=dis[j]+1;   
  26.                   q[++r]=i;  
  27.                }  
  28.      }  
  29.      if (dis[N]>0)  
  30.         return 1;  
  31.      else  
  32.         return 0;//汇点的DIS小于零,表明BFS不到汇点   
  33. }  
  34. //Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广   
  35. int find(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量  
  36. {  
  37.     int i,a=0;  
  38.     if (x==N)return low;//是汇点   
  39.     for (i=1;i<=N;i++)  
  40.     if (tab[x][i] >0 //连通   
  41.      && dis[i]==dis[x]+1 //是分层图的下一层   
  42.      &&(a=find(i,min(low,tab[x][i]))))//能到汇点(a <> 0)   
  43.     {  
  44.        tab[x][i]-=a;  
  45.        tab[i][x]+=a;  
  46.        return a;  
  47.     }  
  48.     return 0;  
  49.       
  50. }  
  51. int main()  
  52. {   
  53.     int i,j,f,t,flow,tans;  
  54.     while (scanf("%d%d",&M,&N)!=EOF){  
  55.     memset(tab,0,sizeof(tab));  
  56.     for (i=1;i<=M;i++)  
  57.     {  
  58.         scanf("%d%d%d",&f,&t,&flow);  
  59.         tab[f][t]+=flow;  
  60.     }  
  61.       
  62.     ANS=0;  
  63.     while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束   
  64.     {  
  65.           while(tans=find(1,0x7fffffff))ANS+=tans;//一次BFS要不停地找增广路,直到找不到为止   
  66.     }  
  67.     printf("%d\n",ANS);  
  68.     }  
  69.     system("pause");  
  70. }  


另一道题目是POJ1742 使用邻接表，采用当前弧优化

[cpp] view plain copy
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <vector>  
  5. #include <queue>  
  6. using namespace std;  
  7. int N, NP, NC, M;  
  8. struct Edge  
  9. {  
  10.     int u, v, cap;  
  11.     Edge() {}  
  12.     Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}  
  13. } es[150 * 150];  
  14. int R, S, T;  
  15. vector<int> tab[109]; // 边集  
  16. int dis[109];  
  17. int current[109];  
  18. void addedge(int u, int v, int cap)  
  19. {  
  20.     tab[u].push_back(R);  
  21.     es[R++] = Edge(u, v, cap); // 正向边  
  22.     tab[v].push_back(R);  
  23.     es[R++] = Edge(v, u, 0); // 反向边容量为0  
  24.     // 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2  
  25. }  
  26. int BFS()  
  27. {  
  28.     queue<int> q;  
  29.     q.push(S);  
  30.     memset(dis, 0x3f, sizeof(dis));  
  31.     dis[S] = 0;  
  32.     while (!q.empty())  
  33.     {  
  34.         int h = q.front();  
  35.         q.pop();  
  36.         for (int i = 0; i < tab[h].size(); i++)  
  37.         {  
  38.             Edge &e = es[tab[h][i]];  
  39.             if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)  
  40.             {  
  41.                 dis[e.v] = dis[h] + 1;  
  42.                 q.push(e.v);  
  43.             }  
  44.         }  
  45.     }  
  46.     return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点  
  47. }  
  48. int dinic(int x, int maxflow)  
  49. {  
  50.     if (x == T)  
  51.         return maxflow;  
  52.     // i = current[x] 当前弧优化  
  53.     for (int i = current[x]; i < tab[x].size(); i++)  
  54.     {  
  55.         current[x] = i;  
  56.         Edge &e = es[tab[x][i]];  
  57.         if (dis[e.v] == dis[x] + 1 && e.cap > 0)  
  58.         {  
  59.             int flow = dinic(e.v, min(maxflow, e.cap));  
  60.             if (flow)  
  61.             {  
  62.                 e.cap -= flow; // 正向边流量降低  
  63.                 es[tab[x][i] ^ 1].cap += flow; // 反向边流量增加  
  64.                 return flow;  
  65.             }  
  66.         }  
  67.     }  
  68.     return 0; // 找不到增广路 退出  
  69. }  
  70. int DINIC()  
  71. {  
  72.     int ans = 0;  
  73.   
  74.     while (BFS()) // 建立分层图  
  75.     {  
  76.         int flow;  
  77.         memset(current, 0, sizeof(current)); // BFS后应当清空当前弧数组  
  78.         while (flow = dinic(S, 0x3f3f3f3f)) // 一次BFS可以进行多次增广  
  79.             ans += flow;  
  80.     }  
  81.     return ans;  
  82. }  
  83. int main()  
  84. {  
  85.     while (scanf("%d%d%d%d", &N, &NP, &NC, &M) != EOF)  
  86.     {  
  87.         R = 0;  
  88.         S = N;  
  89.         T = N + 1;  
  90.         for (int i = 0; i <= T; i++)  
  91.             tab[i].clear();  
  92.         for (int i = 0; i < M; i++)  
  93.         {  
  94.             int u, v, cap;  
  95.             scanf(" (%d,%d)%d", &u, &v, &cap);  
  96.             addedge(u, v, cap);  
  97.         }  
  98.         for (int i = 0; i < NP; i++)  
  99.         {  
  100.             int u, p;  
  101.             scanf(" (%d)%d", &u, &p);  
  102.             addedge(S, u, p);  
  103.         }  
  104.         for (int i = 0; i < NC; i++)  
  105.         {  
  106.             int u, c;  
  107.             scanf(" (%d)%d", &u, &c);  
  108.             addedge(u, T, c);  
  109.         }  
  110.   
  111.         printf("%d\n", DINIC());  
  112.     }  
  113.     return 0;  
  114. }  
标签：

相关文章