EK算法

痛定思痛。 2021-12-08 19:49 156阅读 0赞

Edmonds-Karp算法是最简单的网络流算法，比较慢，时间复杂度为O(V\*E^2)。

具体思路可以参考算法导论。

此算法用广度优先搜索寻找增光路的，代码写起来比较简单。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
      2 #include <queue>
      3 #include <stdio.h>
      4 #include <memory.h>
      5 using namespace std;
      6 const int maxnum=201;
      7 const int maxdata=0x7fffffff;
      8 int f[maxnum][maxnum]; //残留网络的容量
      9 int cf[maxnum];    //标记从源点到当前节点路径上的最小残余容量
     10 int pre[maxnum];     //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列
     11 queue<int> q;
     12 int p,e;
     13 
     14 int bfs(int s,int e)  //EK算法使用BFS寻找增广路径
     15 {
     16     while(!q.empty())
     17         q.pop();
     18     int i;
     19     for(i=1;i<=p;i++)  //初始化前驱
     20         pre[i]=-1;
     21 
     22     cf[s]=maxdata;     //初始化残留容量为最大
     23     q.push(s);
     24     while(!q.empty())
     25     {
     26         int t=q.front();
     27         q.pop();
     28         //cout<<t<<"pop!"<<endl;
     29         if(t==e)      //找到了增广路径
     30             break;
     31         for(i=1;i<=p;i++)     //遍历所有的结点
     32         {
     33             if(i!=s && f[t][i]>0 && pre[i]==-1)
     34             {
     35                 pre[i]=t;      //记录前驱
     36                 cf[i]=min(f[t][i],cf[t]);  //关键：迭代的找到增量
     37                 q.push(i);
     38                 //cout<<i<<" push!"<<endl;
     39             }
     40         }
     41     }
     42     if(pre[e]==-1)   //残留图中不再存在增广路径
     43         return -1;
     44     return cf[e];
     45 }
     46 
     47 int maxflow(int s,int e)
     48 {
     49     int sum=0;
     50     int ans=0;
     51     int p,q;
     52     while(1)
     53     {
     54         ans=bfs(s,e);
     55         cout<<ans<<"!"<<endl;
     56         if(ans==-1)
     57             break;
     58         q=e;
     59         while(q!=s)
     60         {
     61             p=pre[q];
     62             f[p][q]-=ans;  //改变正向边的容量
     63             f[q][p]+=ans;
     64             q=p;
     65         }
     66         sum+=ans;
     67     }
     68     return sum;
     69 }
     70 
     71 void Init()
     72 {
     73     scanf("%d%d",&p,&e);
     74     memset(f,0,sizeof(f));
     75     int i;
     76     int u,v,w;
     77     for(i=0;i<e;i++)
     78     {
     79         scanf("%d%d%d",&u,&v,&w);
     80         f[u][v]=w;
     81     }
     82 }
     83 
     84 int main()
     85 {
     86     Init();
     87     int res=maxflow(1,p);
     88     printf("%d\n",res);
     89     return 0;
     90 }
     91 
     92 /*
     93 6 10
     94 1 2 16
     95 1 3 13
     96 2 3 10
     97 2 4 12
     98 3 2 4
     99 3 5 14
    100 4 3 9
    101 4 6 20
    102 5 4 7
    103 5 6 4
    104 */

转载于:https://www.cnblogs.com/pushing-my-way/archive/2012/08/09/2630615.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/93dec312ba104de1b8b39fd2ad33c9df.png