最近学习了网络流最大流的三种做法，有Ford-Fulkerson，还有EdmondsKarp，Dinic
贴代码，这个是Ford-Fulkerson
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<cstdio> using namespace std; typedef long long LL; const int oo=2147483647; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int maxn=100010; queue <int> Q; int first[maxn],next[maxn],u[maxn],v[maxn],w[maxn],rev[maxn],n,m,vis[maxn],a,b,c; void addEdge(int i,int a,int b,int c,int d) { u[i]=a;v[i]=b;w[i]=c;rev[i]=d; next[i]=first[a];first[a]=i; } int dfs(int x,int t,int a) { if(x==t)return a; vis[x]=1; for(int i=first[x];i!=-1;i=next[i]) if(!vis[v[i]] && w[i]>0) { int d=dfs(v[i],t,min(a,w[i])); if(d>0) { w[i]-=d;w[rev[i]]+=d; return d; } } return 0; } int FF(int s,int t) { int flow=0; while(1) { memset(vis,0,sizeof(vis)); int f=dfs(s,t,oo); if(!f)return flow; flow+=f; } } int main() { memset(first,-1,sizeof(first)); n=read();m=read(); for(int i=0;i<m;i++) { a=read();b=read();c=read(); addEdge(2*i,a,b,c,2*i+1); addEdge(2*i+1,b,a,0,2*i); } printf("%d",FF(1,n)); }
还有EdmondsKarp
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<cstdio> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } queue <int> Q; const int maxn=100010; int first[maxn],next[maxn],u[maxn],v[maxn],w[maxn],rev[maxn],n,m,a,b,c,pre[maxn]; bool vis[maxn]; void addEdge(int i,int a,int b,int c,int d) { u[i]=a;v[i]=b;w[i]=c;rev[i]=d; next[i]=first[a];first[a]=i; } bool BFS(int s,int t) { memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); while(Q.size())Q.pop(); vis[s]=true;Q.push(s); while(Q.size()) { int p=Q.front();Q.pop(); for(int i=first[p];i!=-1;i=next[i]) if(!vis[v[i]] && w[i]>0) { pre[v[i]]=i; vis[v[i]]=1; if(v[i]==t)return 1; Q.push(v[i]); } } return 0; } int EK(int s,int t) { int maxflow=0,d; while(BFS(s,t)) { d=w[pre[t]]; for(int i=pre[t];i!=-1;i=pre[u[i]])d=min(d,w[i]); for(int i=pre[t];i!=-1;i=pre[u[i]])w[i]-=d,w[rev[i]]+=d; maxflow+=d; } return maxflow; } int main() { memset(first,-1,sizeof(first)); n=read();m=read(); for(int i=0;i<m;i++) { a=read();b=read();c=read(); addEdge(2*i,a,b,c,2*i+1); addEdge(2*i+1,b,a,0,2*i); } printf("%d ",EK(1,n)); return 0; }
还有Dinic
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<cstdio> using namespace std; typedef long long LL; const int oo=2147483647; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int maxn=100010; queue <int> Q; int first[maxn],next[maxn],u[maxn],v[maxn],w[maxn],rev[maxn],n,m,cur[maxn],vis[maxn],d[maxn],a,b,c; void addEdge(int i,int a,int b,int c,int d) { u[i]=a;v[i]=b;w[i]=c;rev[i]=d; next[i]=first[a];first[a]=i; } bool bfs(int s,int t) { memset(d,42,sizeof(d)); memset(vis,0,sizeof(vis)); Q.push(s);vis[s]=1;d[s]=0; while(Q.size()) { int p=Q.front();Q.pop(); for(int i=first[p];i!=-1;i=next[i]) if(!vis[v[i]] && w[i]>0) { vis[v[i]]=1; d[v[i]]=d[p]+1; Q.push(v[i]); } } return vis[t]; } int dfs(int x,int t,int a) { if(x==t || a==0)return a; int flow=0,f; for(int& i=cur[x];i!=-1;i=next[i]) if(d[x]+1==d[v[i]] && (f=dfs(v[i],t,min(a,w[i])))>0) { w[i]-=f;w[rev[i]]+=f;a-=f;flow+=f; if(a==0)break; } return flow; } int Dinic(int s,int t) { int flow=0; while(bfs(s,t)) { for(int i=1;i<=n;i++)cur[i]=first[i]; flow+=dfs(s,t,oo); } return flow; } int main() { memset(first,-1,sizeof(first)); n=read();m=read(); for(int i=0;i<m;i++) { a=read();b=read();c=read(); addEdge(2*i,a,b,c,2*i+1); addEdge(2*i+1,b,a,0,2*i); } printf("%d",Dinic(1,n)); }