POJ 1459 Power Network
题意:我就直接给出题目要求的东西吧:
在一个网络图中有n个点,其中有np个发电站,nc个用户,m条电线;每个发电站,用户,和电线都对应有一个最大的电流;让求出该网络中最大的电流;
添加一个源点为(0)和一个汇点(n+1),源点与发电站相连,电流量为发电站的最大电流;用户与汇点相连,电流量为用户需要的最大电流。
思路:最大流的一个简单变形,只要处理好题目给定的数据,直接套用模板就OK了!
AC代码:
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; #define INF 100000000 #define N 202 int cap[N][N],flow[N][N]; int p[N],a[N]; int n,m,np,nc,t; int Edmonds_Karp(int s) { int f=0; queue<int >q; while(1) { memset(a,0,sizeof(a)); a[s]=INF; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int v=1;v<=t;v++) if(!a[v]&&cap[u][v]>flow[u][v]) { p[v]=u; q.push(v); a[v]=min(a[u],cap[u][v]-flow[u][v]); } } if(a[t]==0)break; for(int u=t;u!=s;u=p[u]) { flow[p[u]][u]+=a[t]; flow[u][p[u]]-=a[t]; } f+=a[t]; } return f; } int main() { while(scanf("%d%d%d%d",&n,&np,&nc,&m) != EOF) { int u,v,c; memset(cap,0,sizeof(cap)); memset(flow,0,sizeof(flow)); for(int i=0;i<m;i++) { scanf(" (%d,%d)%d",&u,&v,&c); cap[u+1][v+1]+=c; } for(int i=0;i<np;i++) { scanf(" (%d)%d",&v,&c); cap[0][v+1]+=c; } for(int i=0;i<nc;i++) { scanf(" (%d)%d",&u,&c); cap[u+1][n+1]+=c; } t=n+1; printf("%d\n",Edmonds_Karp(0)); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。