Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.
InputThe first line of input contains an integer T, denoting the number of test cases. 2 3 2 1 2 1 2 3 1 3 3 1 2 1 2 3 1 1 3 1 Sample Output Case 1: 1 Case 2: 2 1 #include <stdio.h> 2 #include <string.h> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 #define inf 0x3f3f3f3f 7 const int maxn=1005; 8 struct node{ 9 int to,nex,cap; 10 }e[maxn<<1]; 11 int deep[maxn],head[maxn],vis[maxn]; 12 int t,n,m,len; 13 void init() 14 { 15 len=0; 16 memset(deep,0,sizeof(deep)); 17 memset(e,0,sizeof(e)); 18 memset(head,-1,sizeof(head)); 19 } 20 void add(int u,int v,int w) 21 { 22 e[len].to=v; 23 e[len].cap=w; 24 e[len].nex=head[u]; 25 head[u]=len++; 26 } 27 bool bfs(int s,int t) 28 { 29 memset(vis,0,sizeof(vis)); 30 queue<int> q; 31 while(!q.empty()) q.pop(); 32 deep[s]=0; 33 vis[s]=1; 34 deep[t]=-1; 35 q.push(s); 36 while(!q.empty()) 37 { 38 int u=q.front(); q.pop(); 39 for(int i=head[u];i!=-1;i=e[i].nex) 40 { 41 int to=e[i].to; 42 if(e[i].cap<=0||vis[to]) continue; 43 vis[to]=1; 44 deep[to]=deep[u]+1; 45 q.push(to); 46 } 47 } 48 if(deep[t]==-1) return false; 49 else return true; 50 } 51 int dfs(int u,int t,int flow) 52 { 53 int res=0; 54 if(u==t||flow==0) return flow; 55 for(int i=head[u];i!=-1;i=e[i].nex) 56 { 57 int to=e[i].to; 58 if(deep[to]==deep[u]+1) 59 { 60 int f=dfs(to,t,min(flow,e[i].cap)); 61 if(f<=0) continue; 62 e[i].cap-=f; 63 e[i^1].cap+=f; 64 flow-=f; 65 res+=f; 66 if(flow!=0) break; 67 } 68 } 69 return res; 70 } 71 int Dinic(int s,int t) 72 { 73 int ans=0; 74 while(bfs(s,t)) 75 { 76 ans+=dfs(s,t,inf); 77 } 78 return ans; 79 } 80 int main() 81 { 82 scanf("%d",&t); 83 for(int j=1;j<=t;j++) 84 { 85 init(); 86 scanf("%d%d",&n,&m); 87 for(int i=1;i<=m;i++) 88 { 89 int u,v,w; 90 scanf("%d%d%d",&u,&v,&w); 91 add(u,v,w); 92 add(v,u,0); 93 } 94 printf("Case %d: %d\n",j,Dinic(1,n)); 95 } 96 }
|
|