CUGB图论专场2:D - Power Network 最大流EK算法
Description
An example is in figure 1. The label x/y of power station u shows that p(u)=x and p max(u)=y. The label x/y of consumer u shows that c(u)=x and cmax(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6.
Input
Output
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20 7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7 (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5 (0)5 (1)2 (3)2 (4)1 (5)4
Sample Output
15 6
Hint
思路:刚开始不理解EK算法中正向与反向边中的加减,所以查找了好多资料,有了前一篇博客的转载才理解其中的意思,所以才完成了这道题,可以说搞了一天了,哎呀,刚才又因为输入的问题卡了好久,晕死……
因为所以的电站都是源点,所有的消费者都是汇点,所以新建一个源点把所有的电站连起来,再新建一个汇点把所有的消费者连起来就行了,我把有的点加1,就是1到n,然后0点为源点,n+1点为汇点,用EK算法就可以算出来了。
EK算法是比较简单的最大流算法,比较好理解,代码比较少。现在一步一步学习最大流算法,今天学习了最大流的所有算法,都理解了其中的意味,不过还没有敲代码,有时间再一个一个算法的敲了。
EK算法中,正向减去,因为流题加上就相当于容量减去,其差是一样的,所以可以直接把容量减去就行了。但是为何其反向边要加上呢,因为如果没有反向边的话,增广路是不能回退的,即可能还存在别的增广路使最大流更加大。比如:1,2,3,4结点之间容量都是1,若1,2,3,4是增广路,然后就不存在增广路了,则最大流为1;但是这个最大流是错的,因为可以过1,2,4这条增广路以及1,3,4这条增广路使得最大流为2.如果加入反向边,那么寻找第一次增广路即1,2,3,4的时候,反向边(3,2)加了一个数,那么就不为0,此时最大流为1;则可以寻找到第二条增广路1,3,2,4,此时最大流为2正确…………(详细的在前一篇博客中有转载的详解)
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <list> #include <queue> #include <string> #include <cstring> #include <map> #include <set> #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define pri(a) printf("%d\n",a) #define MM 10002 #define MN 105 #define INF 168430090 using namespace std; typedef long long ll; int n,m,k,t,ans,pre[MN],vis[MN],Map[MN][MN]; int bfs() { mem(vis,0); queue<int>q; q.push(0); vis[0]=1; while(!q.empty()) //找增广路 { int u=q.front(); q.pop(); for(int v=0;v<=n+1;v++) { if(!vis[v]&&Map[u][v]) { pre[v]=u; //记录前向结点 if(v==n+1) return 1; q.push(v); vis[v] = 1; } } } return 0; } void change() { int i,sum=INF; for(i=n+1; i != 0; i = pre[i]) sum = min(sum,Map[pre[i]][i]); for(i=n+1; i != 0; i = pre[i]) { Map[pre[i]][i]-=sum; //正向边减 Map[i][pre[i]]+=sum; //反向边加 } ans+=sum; } int main() { while(~scanf("%d%d%d%d",&n,&m,&k,&t)) { mem(Map,0); ans=0; int u,v,w; while(t--) { while(getchar()!=‘(‘); scanf("%d,%d)%d",&u,&v,&w); Map[u+1][v+1]+=w; } while(m--) { while(getchar()!=‘(‘); scanf("%d)%d",&u,&w); Map[0][u+1]=w; //新建源点0 } while(k--) { while(getchar()!=‘(‘); scanf("%d)%d",&u,&w); Map[u+1][n+1]=w; //新建汇点n+1 } while(bfs()) change(); pri(ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。