poj 1459 Power Network (dinic)
Time Limit: 2000MS | Memory Limit: 32768K | |
Total Submissions: 23059 | Accepted: 12072 |
Description
An example is in figure 1. The label x/y of power station u shows that p(u)=x and pmax(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 lmax(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
#include"stdio.h" #include"string.h" #include"queue" #include"algorithm" using namespace std; #define N 205 #define inf 100000000 int g[N][N],dis[N]; int min(int a,int b) { return a<b?a:b; } int spfa(int s,int t) { int i; queue<int>q; q.push(s); memset(dis,0,sizeof(dis)); dis[s]=1; while(!q.empty()) { s=q.front(); q.pop(); for(i=0;i<=t;i++) { if(!dis[i]&&g[s][i]) { dis[i]=dis[s]+1; if(i==t) return 1; q.push(i); } } } return 0; } int dfs(int s,int t,int lim) { int i,cost=0,tmp; if(s==t) return lim; for(i=0;i<=t;i++) { if(g[s][i]&&dis[i]==dis[s]+1) { tmp=dfs(i,t,min(lim-cost,g[s][i])); if(tmp>0) { g[s][i]-=tmp; g[i][s]+=tmp; cost+=tmp; if(cost==lim) break; } else dis[i]=-1; } } return cost; } int dinic(int s,int t) { int ans=0; while(spfa(s,t)) ans+=dfs(s,t,inf); return ans; } int main() { int n,np,nc,m,u,v,d,i; char str[30]; while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=-1) { memset(g,0,sizeof(g)); while(m--) { scanf("%s",str); u=v=d=0; for(i=1;str[i]!='\0';i++) { if(str[i]>='0'&&str[i]<='9') u=u*10+str[i]-'0'; else break; } for(i++;str[i]!='\0';i++) { if(str[i]>='0'&&str[i]<='9') v=v*10+str[i]-'0'; else break; } for(i++;str[i]!='\0';i++) { if(str[i]>='0'&&str[i]<='9') d=d*10+str[i]-'0'; else break; } g[u][v]+=d; } while(np--) { scanf("%s",str); u=d=0; for(i=1;str[i]!='\0';i++) { if(str[i]>='0'&&str[i]<='9') u=u*10+str[i]-'0'; else break; } for(i++;str[i]!='\0';i++) { if(str[i]>='0'&&str[i]<='9') d=d*10+str[i]-'0'; else break; } g[n+1][u]+=d; //超级源点 } while(nc--) { scanf("%s",str); u=d=0; for(i=1;str[i]!='\0';i++) { if(str[i]>='0'&&str[i]<='9') u=u*10+str[i]-'0'; else break; } for(i++;str[i]!='\0';i++) { if(str[i]>='0'&&str[i]<='9') d=d*10+str[i]-'0'; else break; } g[u][n+2]+=d; //超级汇点 } int ans=dinic(n+1,n+2); printf("%d\n",ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。