（还是不熟 |好难啊
最大流 裸题
Edmonds_Karp算法（bfs）
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; int m; int g[220][220],pre[220];int bfs(int st,int ed) { for(int i=1;i<=m;i++)pre[i]=-1; int u,w=inf; queue<int>que; que.push(st);pre[st]=0; while(!que.empty()) { u=que.front();que.pop(); if(u==ed)break; for(int i=1;i<=m;i++) { if(pre[i]==-1&&g[u][i]>0) { pre[i]=u; w=min(w,g[u][i]); que.push(i); } } } if(pre[ed]==-1)return 0; return w; } int E_K(int st,int ed) { int w,sum=0; while(w=bfs(st,ed)) { int u=ed; while(u!=st) { g[pre[u]][u]-=w; g[u][pre[u]]+=w; u=pre[u]; } sum+=w; } return sum; } int main() { int n,i,j,k,u,v,w; while(~scanf("%d%d",&n,&m)) { memset(g,0,sizeof(g)); for(i=1;i<=n;i++) { scanf("%d%d%d",&u,&v,&w); g[u][v]+=w; } printf("%d\n",E_K(1,m)); } }
Dinic算法 是E_K算法的优化 可以快一些 （bfs+dfs）
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; int m; int g[220][220],dep[220]; bool bfs(int st,int ed) { for(int i=1;i<=m;i++)dep[i]=-1; int u; queue<int>que; que.push(st);dep[st]=0; while(!que.empty()) { u=que.front();que.pop(); for(int i=1;i<=m;i++) { if(dep[i]==-1&&g[u][i]>0) { dep[i]=dep[u]+1; if(i==ed)return 1; que.push(i); } } } return dep[ed]!=-1; } int dfs(int st,int ed,int lim) { if(!lim||st==ed)return lim; int w=0,d; for(int i=1;i<=m;i++) { if(dep[i]==dep[st]+1&&g[st][i]>0&&(d=dfs(i,ed,min(g[st][i],lim)))) { g[st][i]-=d; g[i][st]+=d; w+=d; lim-=d; if(!lim)break; } } return w; } int Dinic(int st,int ed) { int sum=0; while(bfs(st,ed))sum+=dfs(st,ed,inf); return sum; } int main() { int n,i,j,k,u,v,w; while(~scanf("%d%d",&n,&m)) { memset(g,0,sizeof(g)); for(i=1;i<=n;i++) { scanf("%d%d%d",&u,&v,&w); g[u][v]+=w; } printf("%d\n",Dinic(1,m)); } }
LOJ「网络流 24 题」搭配飞行员 （第一题
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; int n,m; int g[110][110],dep[110]; bool bfs(int st,int ed) { for(int i=0;i<=n;i++)dep[i]=-1; int u; queue<int>que; que.push(st);dep[st]=0; while(!que.empty()) { u=que.front();que.pop(); for(int i=1;i<=n;i++) { if(dep[i]==-1&&g[u][i]>0) { dep[i]=dep[u]+1; if(i==ed)return 1; que.push(i); } } } return dep[ed]!=-1; } int dfs(int st,int ed,int lim) { if(!lim||st==ed)return lim; int w=0,d; for(int i=0;i<=n;i++) { if(dep[i]==dep[st]+1&&g[st][i]>0&&(d=dfs(i,ed,min(g[st][i],lim)))) { g[st][i]-=d; g[i][st]+=d; w+=d; lim-=d; if(!lim)break; } } return w; } int Dinic(int st,int ed) { int sum=0; while(bfs(st,ed))sum+=dfs(st,ed,inf); return sum; } int main() { int i,j,k,u,v; scanf("%d%d",&n,&m); // scanf("%d",&k); for(i=1;i<=m;i++)g[0][i]=1; for(i=m+1;i<=n;i++)g[i][n+1]=1; n++; // while(k--) while(~scanf("%d%d",&u,&v)) { // scanf("%d%d",&u,&v); g[u][v]=1; } printf("%d\n",Dinic(0,n)); }
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; int n,m; int g[110][110],dep[110]; bool bfs(int st,int ed) { for(int i=0;i<=n;i++)dep[i]=-1; int u; queue<int>que; que.push(st);dep[st]=0; while(!que.empty()) { u=que.front();que.pop(); for(int i=1;i<=n;i++) { if(dep[i]==-1&&g[u][i]>0) { dep[i]=dep[u]+1; if(i==ed)return 1; que.push(i); } } } return dep[ed]!=-1; } int dfs(int st,int ed,int lim) { if(!lim||st==ed)return lim; int w=0,d; for(int i=0;i<=n;i++) { if(dep[i]==dep[st]+1&&g[st][i]>0&&(d=dfs(i,ed,min(g[st][i],lim)))) { g[st][i]-=d; g[i][st]+=d; w+=d; lim-=d; if(!lim)break; } } return w; } int Dinic(int st,int ed) { int sum=0; while(bfs(st,ed))sum+=dfs(st,ed,inf); return sum; } int main() { int i,j,k,u,v; scanf("%d%d",&m,&n); for(i=1;i<=m;i++)g[0][i]=1; for(i=m+1;i<=n;i++)g[i][n+1]=1; n++; scanf("%d%d",&u,&v); while(u!=-1&&v!=-1) { g[u][v]=1; scanf("%d%d",&u,&v); } k=Dinic(0,n); if(k==0)puts("No solution!"); else { printf("%d\n",k); for(i=1;i<=m;i++) { for(j=m+1;j<=n;j++) if(g[j][i]!=0)printf("%d %d\n",i,j); } } }
好艰难 我觉得我只会 对着模板抄
求最大流量下的最小费用
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; struct P{ int to,flow,dis,next; }p[50500<<1]; int head[50500<<1],pnum; void add(int from,int to,int flow,int dis) { p[++pnum].next=head[from]; p[pnum].to=to; p[pnum].flow=flow; p[pnum].dis=dis; head[from]=pnum; } int dis[5050],vis[5050],pre[5050],last[5050],flow[5050]; bool spaf_bfs(int s,int t) { memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(flow,inf,sizeof(flow)); queue<int> que; que.push(s);dis[s]=0;pre[t]=-1;vis[s]=1; while(!que.empty()) { int u=que.front();que.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=p[i].next) { if(p[i].flow>0&&dis[p[i].to]>dis[u]+p[i].dis) { dis[p[i].to]=dis[u]+p[i].dis; pre[p[i].to]=u; last[p[i].to]=i; flow[p[i].to]=min(flow[u],p[i].flow); if(!vis[p[i].to]) { vis[p[i].to]=1; que.push(p[i].to); } } } } return pre[t]!=-1; } void solve(int s,int t,int &w,int &c) { w=0;c=0; while(spaf_bfs(s,t)) { int u=t; w+=flow[t]; c+=flow[t]*dis[t]; while(u!=s) { p[last[u]].flow-=flow[t]; p[last[u]^1].flow+=flow[t]; u=pre[u]; } } } int main() { memset(head,-1,sizeof(head));pnum=-1; int n,m,s,t,i,u,v,w,f; scanf("%d%d%d%d",&n,&m,&s,&t); for(i=1;i<=m;i++) { scanf("%d%d%d%d",&u,&v,&w,&f); add(u,v,w,f); add(v,u,0,-f); } solve(s,t,u,v); printf("%d %d\n",u,v); }
最大流+二分
借着别人的博客的二分 总算补完了这一题。
（用E_K算法会超时，用Dinic不会）
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; struct P{ int next,to,flow; }p[22200<<1]; int head[22200<<1],pnum; struct PP{ int u,v,t; PP(){} PP(int uu,int vv,int tt){u=uu;v=vv;t=tt;} }pp[20200]; void add(int from,int to,int flow) { p[++pnum].next=head[from]; p[pnum].to=to; p[pnum].flow=flow; head[from]=pnum; } int x,y,c,n,allsum,a[2020],b[2020]; int pre[2020],dep[2020]; bool vis[2020]; bool bfs(int st,int ed) { memset(dep,-1,sizeof(dep)); int u; queue<int>que; que.push(st);dep[st]=0; while(!que.empty()) { u=que.front();que.pop(); for(int i=head[u];i!=-1;i=p[i].next) { if(dep[p[i].to]==-1&&p[i].flow) { dep[p[i].to]=dep[u]+1; if(p[i].to==ed)return 1; que.push(p[i].to); } } } return dep[ed]!=-1; } int dfs(int st,int ed,int lim) { if(!lim||st==ed)return lim; int w=0,d; for(int i=head[st];i!=-1;i=p[i].next) { if(dep[p[i].to]==dep[st]+1&&(d=dfs(p[i].to,ed,min(p[i].flow,lim)))) { p[i].flow-=d; p[i^1].flow+=d; w+=d; lim-=d; if(!lim)break; } } return w; } int Dinic(int st,int ed) { int sum=0; while(bfs(st,ed))sum+=dfs(st,ed,inf); return sum; } /* int bfs(int st,int ed) { memset(vis,0,sizeof(vis)); int u,w=inf; queue<int>que; que.push(st);pre[st]=pre[ed]=-1;vis[st]=1; while(!que.empty()) { u=que.front();que.pop(); if(u==ed)break; for(int i=head[u];i!=-1;i=p[i].next) { if(vis[p[i].to]==0&&p[i].flow>0) { vis[p[i].to]=1; pre[p[i].to]=i; w=min(w,p[i].flow); que.push(p[i].to); } } } if(pre[ed]==-1)return 0; return w; } int E_K(int st,int ed) { int w,sum=0; while(w=bfs(st,ed)) { for(int i=pre[ed];i!=-1;i=pre[p[i^1].to]) { p[i].flow-=w; p[i^1].flow+=w; } sum+=w; } return sum; }*/ bool check(int mid) { int i; memset(head,-1,sizeof(head));pnum=-1; for(i=1;i<=y;i++) { add(0,i,a[i]); add(i,0,0); } for(i=1;i<=x;i++) { add(y+i,n,b[i]); add(n,y+i,0); } for(i=1;i<=c;i++) { if(pp[i].t<=mid) { add(pp[i].u,pp[i].v+y,inf); add(pp[i].v+y,pp[i].u,0); } } int maxflow=Dinic(0,n); if(maxflow==allsum)return 1; return 0; } int main() { allsum=0; int i,j,k,w; int u,v,t,l,r=0,mid,ans; scanf("%d%d%d",&x,&y,&c); n=x+y+1; for(i=1;i<=x;i++) { scanf("%d",&b[i]); allsum+=b[i]; } for(i=1;i<=y;i++)scanf("%d",&a[i]); for(i=1;i<=c;i++) { scanf("%d%d%d",&v,&u,&t); pp[i]=PP(u,v,t); r=max(r,t); } l=0;ans=-1;r++; while(l<r) { mid=(l+r)>>1; if(check(mid)) { ans=mid; r=mid; } else l=mid+1; } printf("%d\n",ans); }