前言：
关于网络流，按董大佬的话，就是个板子，会打也没用
正文：
最大流
最大流的基础求法就是増广路算法（$EK$）
虽然它跑的慢，但也要会打，因为可以魔改求费用流
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using std::queue; const int maxn=11111; #define inf (0x3f3f3f3f) class Max_Flow { private: struct edge { int to,next,cap; edge(){} edge(int to,int next,int cap):to(to),next(next),cap(cap){} }; edge e[maxn*20]; int cnt,head[maxn]; void add(int from,int to,int cap) { e[++cnt]=edge(to,head[from],cap); head[from]=cnt; } struct node { int pre,kth; }; node p[maxn]; bool vis[maxn]; bool bfs(int s,int t) { memset(p,0,sizeof(p)); memset(vis,0,sizeof(vis)); queue<int>q; q.push(s); p[s].pre=s; vis[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(!vis[v]&&e[i].cap) { vis[v]=1; p[v].pre=u; p[v].kth=i; if(v==t) return 1; q.push(v); } } } return 0; } public: Max_Flow() { cnt=-1; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { add(u,v,w); add(v,u,0); } int EK(int s,int t) { int maxflow=0; while(bfs(s,t)) { int minn=inf; for(int i=t;i!=s;i=p[i].pre) minn=std::min(minn,e[p[i].kth].cap); for(int i=t;i!=s;i=p[i].pre) { e[p[i].kth].cap-=minn; e[p[i].kth^1].cap+=minn; } maxflow+=minn; } return maxflow; } }flow; int main() { int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1,u,v,w;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); flow.addedge(u,v,w); } printf("%d\n",flow.EK(s,t)); return 0; }
当然 $EK$ 的效率显然无法满足我们的要求
所以我们要进行优化，先将图进行分层，再去増广
于是我们有了 $Dinic$ 算法，还有基于它的各种鬼畜优化
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using std::queue; const int maxn=11111; #define inf (0x3f3f3f3f) class Max_Flow { private: struct edge { int to,next,cap; edge(){} edge(int to,int next,int cap):to(to),next(next),cap(cap){} }; edge e[maxn*20]; int cnt,head[maxn]; void add(int from,int to,int cap) { e[++cnt]=edge(to,head[from],cap); head[from]=cnt; } int deep[maxn]; bool bfs(int s,int t) { memset(deep,0,sizeof(deep)); queue<int>q; q.push(s); deep[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(!deep[v]&&e[i].cap) { deep[v]=deep[u]+1; if(v==t) return 1; q.push(v); } } } return 0; } int dfs(int u,int limit,int t) { if(u==t||!limit) return limit; int sum=0; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to;//关于当前弧优化，我并不会 if(deep[v]==deep[u]+1&&e[i].cap) { int flow=dfs(v,std::min(limit-sum,e[i].cap),t); if(!flow) deep[v]=0;//据说叫炸点优化，感觉好霸气的样子 sum+=flow; e[i].cap-=flow; e[i^1].cap+=flow; if(sum==limit) break;//这句剪枝一定要加上，否则会慢很多 } } return sum; } public: Max_Flow() { cnt=-1; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int c) { add(u,v,c); add(v,u,0); } int Dinic(int s,int t) { int maxflow=0; while(bfs(s,t)) { maxflow+=dfs(s,inf,t); } return maxflow; } }flow; int main() { int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1,u,v,c;i<=m;i++) { scanf("%d%d%d",&u,&v,&c); flow.addedge(u,v,c); } printf("%d\n",flow.Dinic(s,t)); return 0; }
费用流
关于费用流，就是将 $EK$ 的 $bfs$ 魔改为 $spfa$ ，每次増广出一条最短路
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using std::queue; const int maxn=5555; #define inf (0x3f3f3f3f) class Mincost_Maxflow { private: struct edge { int to,next,cap,dis; edge(){} edge(int to,int next,int cap,int dis):to(to),next(next),cap(cap),dis(dis){} }; edge e[maxn*20]; int cnt,head[maxn]; void add(int from,int to,int cap,int dis) { e[++cnt]=edge(to,head[from],cap,dis); head[from]=cnt; } struct node { int pre,kth; }; node p[maxn]; int dis[maxn]; bool vis[maxn]; bool spfa(int s,int t) { memset(p,0,sizeof(p)); memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); queue<int>q; q.push(s); p[s].pre=s; dis[s]=0,vis[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(dis[v]>dis[u]+e[i].dis&&e[i].cap) { dis[v]=dis[u]+e[i].dis; p[v].pre=u; p[v].kth=i; if(!vis[v]) { q.push(v); vis[v]=1; } } } } return p[t].pre; } public: int mincost,maxflow; Mincost_Maxflow() { cnt=-1; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int c,int w) { add(u,v,c,w); add(v,u,0,-w); } void mincost_maxflow(int s,int t) { while(spfa(s,t)) { int minn=inf; for(int i=t;i!=s;i=p[i].pre) minn=std::min(minn,e[p[i].kth].cap); for(int i=t;i!=s;i=p[i].pre) { e[p[i].kth].cap-=minn; e[p[i].kth^1].cap+=minn; } maxflow+=minn; mincost+=minn*dis[t]; } } }flow; int main() { int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1,u,v,c,w;i<=m;i++) { scanf("%d%d%d%d",&u,&v,&c,&w); flow.addedge(u,v,c,w); } flow.mincost_maxflow(s,t); printf("%d %d\n",flow.maxflow,flow.mincost); return 0; }
后序：
关于最大流的 $ISAP$ 算法和 $HLPP$ 预流推进以及 $zkw$ 费用流
因为我太菜了，所以都没学，想学的话可以私聊这位大佬