Time Limit: 2000MS | Memory Limit: 32768K | |
Total Submissions: 27831 | Accepted: 14469 |
Description
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
Source
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 #include<vector> 6 using namespace std; 7 int n,np,nc,m,map[105][105],dep[105]; 8 bool vis[105]; 9 bool BFS(){ 10 memset(dep,-1,sizeof dep ); 11 dep[n]=0;queue<int>q;q.push(n); 12 while(!q.empty()){ 13 int u=q.front();q.pop(); 14 for(int v=0;v<=n+1;v++) 15 if(map[u][v]>0&&dep[v]==-1){ 16 dep[v]=dep[u]+1; 17 if(v==n+1)return 1; 18 else q.push(v); 19 } 20 } 21 return 0; 22 } 23 int Dinic(){ 24 vector<int>q;int maxf=0; 25 while(BFS()){ 26 q.push_back(n); 27 memset(vis,0,sizeof(vis));vis[n]=1; 28 while(!q.empty()){ 29 int p=q.back(); 30 if(p==n+1){ 31 int minx=0x7f,minn; 32 for(int i=1;i<q.size();i++){ 33 int u=q[i-1],v=q[i]; 34 if(map[u][v]<minx){ 35 minx=map[u][v];minn=u; 36 } 37 } 38 maxf+=minx; 39 for(int i=1;i<q.size();i++){ 40 int u=q[i-1],v=q[i]; 41 map[u][v]-=minx;map[v][u]+=minx; 42 } 43 while(!q.empty()&&q.back()!=minn){ 44 vis[q.back()]=0;q.pop_back(); 45 } 46 } 47 else { 48 int i; 49 for(i=0;i<=n+1;i++){ 50 if(map[p][i]>0&&!vis[i] 51 &&dep[i]==dep[p]+1){ 52 vis[i]=1;q.push_back(i); 53 break; 54 } 55 } 56 if(i>n+1)q.pop_back(); 57 } 58 } 59 } 60 return maxf; 61 } 62 int main(){ 63 char s[35]; 64 while(scanf("%d%d%d%d",&n,&np,&nc,&m)==4){ 65 memset(map,0,sizeof(map)); 66 for(int i=0,u,v,w;i<m;i++){ 67 scanf("%s",s); 68 sscanf(s,"(%d,%d)%d",&u,&v,&w); 69 map[u][v]+=w; 70 } 71 for(int i=0,v,w;i<np;i++){ 72 scanf("%s",s); 73 sscanf(s,"(%d)%d",&v,&w); 74 map[n][v]+=w; 75 } 76 for(int i=0,v,w;i<nc;i++){ 77 scanf("%s",s); 78 sscanf(s,"(%d)%d",&v,&w); 79 map[v][n+1]+=w; 80 } 81 printf("%d\n",Dinic()); 82 } 83 return 0; 84 }
需要注意:
while(scanf("%d%d%d%d",&n,&np,&nc,&m))
”while(scanf("%d%d%d%d",&n,&np,&nc,&m)==4)
原文:http://www.cnblogs.com/suishiguang/p/6485998.html