最大流
模板：
-
P3376 【模板】网络最大流
#include<bits/stdc++.h> #define int long long using namespace std; const int inf=1e9; int n,m,s,t; int u,v,w; int h[2000004]; struct node{int to,nxt,w; }z[2000004]; int dis[2000004]; int cnt=1; int cur[2000004]; void add(int a,int b,int w){z[++cnt].to=b;z[cnt].nxt=h[a];h[a]=cnt;z[cnt].w=w;z[++cnt].to=a;z[cnt].nxt=h[b];h[b]=cnt;z[cnt].w=0; } bool bfs(){for(int i=1;i<=n;i++) dis[i]=0;queue<int> p;p.push(s);dis[s]=1;while(!p.empty()){int x=p.front();p.pop();for(int i=h[x];i;i=z[i].nxt){int y=z[i].to;if(z[i].w&&!dis[y]){p.push(y);dis[y]=dis[x]+1;if(y==t) return 1;}}}return 0; } int dfs(int x,int flow){if(x==t) return flow;int res=flow;for(int i=cur[x];i&&res;i=z[i].nxt){int y=z[i].to;cur[x]=i;if(dis[y]==dis[x]+1&&z[i].w){int k=dfs(y,min(res,z[i].w));if(!k) dis[y]=0;z[i].w-=k;z[i^1].w+=k;res-=k;}}return flow-res; } signed main(){cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){cin>>u>>v>>w;add(u,v,w);}int flo=0,maxx=0;while(bfs()){for(int i=1;i<=n;i++) cur[i]=h[i];while(flo=dfs(s,(1<<29))){maxx+=flo;}}cout<<maxx; }
费用流
模板：
-
P3381 【模板】最小费用最大流
#include<bits/stdc++.h> using namespace std; int n,m,s,t; int u,v,w,c; int cnt=1; int head[1000004]; int h[1000004]; int cur[1000004]; struct node{int to,nxt,w,c; }z[2000004]; void add(int x,int y,int w,int c){z[++cnt].to=y;z[cnt].nxt=head[x];head[x]=cnt;z[cnt].c=c;z[cnt].w=w;z[++cnt].to=x;z[cnt].nxt=head[y];head[y]=cnt;z[cnt].w=0;z[cnt].c=-c; } bool vis[1000004]; int dis[1000004]; void SPFA(){memset(h,0x3f3f3f3f,sizeof h);queue<int> p;p.push(s);vis[s]=1;while(!p.empty()){int x=p.front();p.pop();vis[x]=0;for(int i=head[x];i;i=z[i].nxt){int y=z[i].to;if(z[i].w&&h[y]>h[x]+z[i].c){h[y]=h[x]+z[i].c;if(!vis[y]){vis[y]=1;p.push(y);}}}} } typedef pair<int,int> pii; int ans1,ans2; const int inf=0x3f3f3f3f; bool dijie(){memset(dis,inf,sizeof dis);memset(vis,0,sizeof vis);priority_queue<pii,vector<pii>,greater<pii> > p;dis[s]=0;p.push({0,s});while(!p.empty()){int x=p.top().second;p.pop();if(vis[x]) continue;vis[x]=1;for(int i=head[x];i;i=z[i].nxt){int y=z[i].to;if(z[i].w&&dis[y]>dis[x]+z[i].c+h[x]-h[y]){dis[y]=dis[x]+h[x]-h[y]+z[i].c;p.push({dis[y],y});}}}return dis[t]!=inf; } int dfs(int x,int flow){int res=flow;if(x==t) return flow;vis[x]=1;for(int i=cur[x];i;i=z[i].nxt){cur[x]=i;int y=z[i].to;if(z[i].w&&h[y]==h[x]+z[i].c&&!vis[y]){int k=dfs(y,min(res,z[i].w));z[i].w-=k;z[i^1].w+=k;res-=k;ans2+=k*z[i].c;if(!res) break;}}vis[x]=0;return flow-res; } signed main(){ios::sync_with_stdio(false);cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){cin>>u>>v>>w>>c;add(u,v,w,c);}SPFA();while(dijie()){ for(int i=1;i<=n;i++) cur[i]=head[i],vis[i]=0,h[i]+=dis[i];ans1+=dfs(s,inf);}cout<<ans1<<" "<<ans2<<endl; }
上下界网络流
无源汇有上下界最大流
模板：
- Loj 116
#include<bits/stdc++.h> using namespace std; const int inf=1e8; int n,m,s,t; int sum; int S,T; struct EDGE{int u,v,down,up; }E[10000004]; struct node{int to,nxt,w; }z[10000004]; int cnt=1; int h[10000004]; int cur[10000004]; int dis[10000004]; int in[1000004]; int out[10000004]; void add(int x,int y,int w){z[++cnt].to=y;z[cnt].nxt=h[x];h[x]=cnt;z[cnt].w=w;z[++cnt].to=x;z[cnt].nxt=h[y];h[y]=cnt;z[cnt].w=0; } bool BFS(){queue<int> p;for(int i=0;i<=n+1;i++) dis[i]=0;p.push(S);dis[S]=1;while(!p.empty()){int x=p.front();p.pop();for(int i=h[x];i;i=z[i].nxt){int y=z[i].to;if(z[i].w&&!dis[y]){dis[y]=dis[x]+1;p.push(y);if(y==T) return 1; }}}return 0; } int dfs(int x,int flow){int res=flow;if(x==T) return res;for(int i=cur[x];i&&res;i=z[i].nxt){int y=z[i].to;cur[x]=i;if(z[i].w&&dis[y]==dis[x]+1){int k=dfs(y,min(res,z[i].w));if(!k) dis[y]=0;z[i].w-=k;z[i^1].w+=k;res-=k;}}return flow-res; } int Dinic(){int flow=0,maxx=0;while(BFS()){for(int i=0;i<=n+1;i++) cur[i]=h[i];while(flow=dfs(S,inf)) maxx+=flow;}return maxx; } signed main(){cin>>n>>m>>s>>t;S=0,T=n+1;for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].down>>E[i].up;for(int i=1;i<=m;i++) {in[E[i].v]+=E[i].down;out[E[i].u]+=E[i].down;}for(int i=1;i<=m;i++) add(E[i].u,E[i].v,E[i].up-E[i].down);for(int i=1;i<=n;i++){if(in[i]>out[i]) add(S,i,in[i]-out[i]),sum+=in[i]-out[i];else add(i,T,out[i]-in[i]);}add(t,s,inf);int k=Dinic(); //cout<<k<<" "<<sum<<endl;if(k!=sum){cout<<"please go home to sleep\n";return 0;}k=z[cnt].w;z[cnt].w=0;z[cnt^1].w=0;for(int i=h[S];i;i=z[i].nxt) z[i].w=z[i^1].w=0;for(int i=h[T];i;i=z[i].nxt) z[i].w=z[i^1].w=0;S=s,T=t;k+=Dinic();cout<<k; }
有源汇有上下界最小流
模板：
-
Loj 117
#include<bits/stdc++.h> using namespace std; const int inf=1e8; int n,m,s,t; int sum; int S,T; struct EDGE{int u,v,down,up; }E[10000004]; struct node{int to,nxt,w; }z[10000004]; int cnt=1; int h[10000004]; int cur[10000004]; int dis[10000004]; int in[1000004]; int out[10000004]; void add(int x,int y,int w){z[++cnt].to=y;z[cnt].nxt=h[x];h[x]=cnt;z[cnt].w=w;z[++cnt].to=x;z[cnt].nxt=h[y];h[y]=cnt;z[cnt].w=0; } bool BFS(){queue<int> p;for(int i=0;i<=n+1;i++) dis[i]=0;p.push(S);dis[S]=1;while(!p.empty()){int x=p.front();p.pop();for(int i=h[x];i;i=z[i].nxt){int y=z[i].to;if(z[i].w&&!dis[y]){dis[y]=dis[x]+1;p.push(y);if(y==T) return 1; }}}return 0; } int dfs(int x,int flow){int res=flow;if(x==T) return res;for(int i=cur[x];i&&res;i=z[i].nxt){int y=z[i].to;cur[x]=i;if(z[i].w&&dis[y]==dis[x]+1){int k=dfs(y,min(res,z[i].w));if(!k) dis[y]=0;z[i].w-=k;z[i^1].w+=k;res-=k;}}return flow-res; } int Dinic(){int flow=0,maxx=0;while(BFS()){for(int i=0;i<=n+1;i++) cur[i]=h[i];while(flow=dfs(S,inf)) maxx+=flow;}return maxx; } signed main(){cin>>n>>m>>s>>t;S=0,T=n+1;for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].down>>E[i].up;for(int i=1;i<=m;i++) {in[E[i].v]+=E[i].down;out[E[i].u]+=E[i].down;}for(int i=1;i<=m;i++) add(E[i].u,E[i].v,E[i].up-E[i].down);for(int i=1;i<=n;i++){if(in[i]>out[i]) add(S,i,in[i]-out[i]),sum+=in[i]-out[i];else add(i,T,out[i]-in[i]);}add(t,s,inf);int k=Dinic(); //cout<<k<<" "<<sum<<endl;if(k!=sum){cout<<"please go home to sleep\n";return 0;}k=z[cnt].w;z[cnt].w=0;z[cnt^1].w=0;for(int i=h[S];i;i=z[i].nxt) z[i].w=z[i^1].w=0;for(int i=h[T];i;i=z[i].nxt) z[i].w=z[i^1].w=0;S=t,T=s;k-=Dinic();cout<<k; }
无源汇有上下界可行流
模板：
-
Loj 115
#include<bits/stdc++.h> using namespace std; struct EDGE{int u,v,up,down; }E[10000004]; struct flow{int nxt,to,w; }z[10000004]; int h[10000004]; int cnt=1; void add(int x,int y,int w){z[++cnt].to=y;z[cnt].nxt=h[x];h[x]=cnt;z[cnt].w=w;z[++cnt].to=x;z[cnt].nxt=h[y];h[y]=cnt;z[cnt].w=0; } int s,S,T; int n,m; int in[10000004]; int out[10000004]; int cur[10000004]; int dis[10000004]; bool BFS(){queue<int> p;for(int i=1;i<=T;i++) dis[i]=0;dis[S]=1;p.push(S);while(!p.empty()){int x=p.front();p.pop();for(int i=h[x];i;i=z[i].nxt){int y=z[i].to;if(!dis[y]&&z[i].w){dis[y]=dis[x]+1;p.push(y);if(y==T) return 1;}}}return 0; } int dfs(int x,int flow){if(x==T) return flow;int res=flow;for(int i=cur[x];i&&res;i=z[i].nxt){int y=z[i].to;cur[x]=i;if(z[i].w&&dis[y]==dis[x]+1){int k=dfs(y,min(res,z[i].w));if(!k) dis[y]=0;z[i].w-=k;z[i^1].w+=k;res-=k;}}return flow-res; } int Dinic(){int maxx=0,flo=0;while(BFS()){for(int i=S;i<=T;i++) cur[i]=h[i];while(flo=dfs(S,(1<<29))) maxx+=flo;}return maxx; } signed main(){cin>>n>>m;T=n+1;for(int i=1;i<=m;i++){cin>>E[i].u>>E[i].v>>E[i].down>>E[i].up;}for(int i=1;i<=m;i++) in[E[i].v]+=E[i].down,out[E[i].u]+=E[i].down;for(int i=1;i<=m;i++) add(E[i].u,E[i].v,E[i].up-E[i].down);for(int i=1;i<=n;i++){if(in[i]>=out[i]) add(S,i,in[i]-out[i]),s+=in[i]-out[i];else add(i,T,out[i]-in[i]);}int k=Dinic();// cout<<k<<" "<<s<<endl;if(k==s) puts("YES");else {puts("NO");return 0;}for(int i=2;i<=2*m+1;i+=2 ){cout<<E[i/2].down+z[i^1].w<<"\n";} }