1、
1 #include<bits/stdc++.h> 2 #define MAX_V 10050 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 typedef long long ll; 6 int n,m,s,t; 7 struct edge{ 8 int to,cap,rev; 9 }; 10 vector<edge>G[MAX_V]; 11 bool used[MAX_V]; 12 void add_edge(int from,int to,int cap){ 13 G[from].push_back((edge){to,cap,G[to].size()}); 14 G[to].push_back((edge){from,0,G[from].size()-1}); 15 } 16 int dfs(int v,int t,int f){ 17 if(v==t)return f; 18 used[v]=true; 19 for(int i=0;i<G[v].size();i++){ 20 edge &e=G[v][i]; 21 if(!used[e.to]&&e.cap>0){ 22 int d=dfs(e.to,t,min(f,e.cap)); 23 if(d>0){ 24 e.cap-=d; 25 G[e.to][e.rev].cap+=d; 26 return d; 27 } 28 } 29 } 30 return 0; 31 } 32 int max_flow(int s,int t){ 33 int flow=0; 34 while(1){ 35 memset(used,0,sizeof used); 36 int f=dfs(s,t,inf); 37 if(f==0) return flow; 38 flow+=f; 39 } 40 } 41 42 int main(){ 43 int t,u,v,f; 44 scanf("%d",&t); 45 for(int ca=1;ca<=t;ca++){ 46 memset(G,0,sizeof G); 47 scanf("%d%d",&n,&m); 48 for(int i=0;i<m;i++){ 49 scanf("%d%d%d",&u,&v,&f); 50 add_edge(u-1,v-1,f); 51 } 52 s=1-1,t=n-1; 53 int ans=max_flow(s,t); 54 printf("Case %d: %d ",ca,ans); 55 } 56 return 0; 57 }
2、
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct Edge{ 4 int to; 5 int w; 6 int nxt; 7 }e[5000005]; 8 int n,m,s,t,tot; 9 int head[5005]; 10 int d[5005]; 11 void add_edge(int u,int v,int w){ 12 e[tot].to=v; 13 e[tot].w=w; 14 e[tot].nxt=head[u]; 15 head[u]=tot++; 16 e[tot].to=u; 17 e[tot].w=0; 18 e[tot].nxt=head[v]; 19 head[v]=tot++; 20 } 21 bool bfs(){ 22 queue<int>Q; 23 Q.push(s); 24 memset(d,0,sizeof d); 25 d[s]=1; 26 while(!Q.empty()){ 27 int u=Q.front(); 28 Q.pop(); 29 for(int i=head[u];i!=-1;i=e[i].nxt){ 30 int v=e[i].to; 31 if(d[v]==0&&e[i].w>0){ 32 d[v]=d[u]+1; 33 Q.push(v); 34 } 35 } 36 } 37 return d[t]!=0; 38 } 39 40 int dfs(int u,int flow){ 41 if(u==t)return flow; 42 int ans=0,x=0; 43 for(int i=head[u];i!=-1;i=e[i].nxt){ 44 int v=e[i].to; 45 if (e[i].w>0&&d[v]==d[u]+1){ 46 x=dfs(v,min(flow-ans,e[i].w)); 47 ans+=x; 48 e[i].w-=x; 49 e[i^1].w+=x; 50 if(ans==flow) return flow; 51 } 52 } 53 if(ans==0) d[u]=0; 54 return ans; 55 } 56 57 int dinic(){ 58 int ans=0; 59 while(bfs()) ans+=dfs(s,INT_MAX); 60 return ans; 61 } 62 63 int main(){ 64 int t,u,v,f; 65 scanf("%d",&t); 66 while(t--){ 67 memset(head,-1,sizeof head); 68 tot=0; 69 scanf("%d%d",&n,&m); 70 for(int i=0;i<m;i++){ 71 scanf("%d%d%d",&u,&v,&f); 72 add_edge(u-1,v-1,f); 73 } 74 s=0,t=n-1; 75 int ans=dinic(); 76 printf("%d ",ans); 77 } 78 return 0; 79 }