模板
标准网络流 （简略）
这里只讲 Dinic。
通过 BFS 不断求出增广路（流量不为零的路径），并记录到原点的距离。然后跑 DFS，往距离增大的方向跑以保证时间复杂度。把增广路上的边减去通过的流量，其反边加上通过的流量。不断重复上述过程直到无法找到新的的增广路。
时间复杂度为 \(O(n^2m)\)，通常跑不满，特殊图的情况下会更快。
参考实现代码
#include<bits/stdc++.h>
#define fst first
#define sec second
#define mkp(a,b) make_pair(a,b)
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int maxn=205,maxm=10200,inf=1e9+1;
const LL linf=1e18+1;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
struct FLOW{int head[maxn],nxt[maxm<<1];tuple<int,LL> e[maxm<<1];int mp_cnt=-1;void init_mp(){memset(head,-1,sizeof(head));mp_cnt=-1;}void add_edge(int u,int v,LL c){e[++mp_cnt]=make_tuple(v,c);nxt[mp_cnt]=head[u],head[u]=mp_cnt;e[++mp_cnt]=make_tuple(u,0);nxt[mp_cnt]=head[v],head[v]=mp_cnt;}int n,s,t;int dis[maxn],cur[maxn];void init(int ni,int si,int ti){init_mp(),n=ni,s=si,t=ti;}bool bfs(){queue<int> q;q.push(s);fill(dis+1,dis+n+1,inf),dis[s]=0;while(!q.empty()){int u=q.front(); q.pop();if(u==t) return true;for(int i=head[u];~i;i=nxt[i]){int v; LL c; tie(v,c)=e[i];if(c&&dis[u]+1<dis[v]){dis[v]=dis[u]+1;q.push(v);}}}return false;}LL dfs(int u,LL f){if(u==t) return f;LL sum=0;for(int i=cur[u];(~i)&&f;i=nxt[i]){int v; LL c; tie(v,c)=e[i],cur[u]=i;if(dis[v]!=dis[u]+1||(!c)) continue;LL fi=dfs(v,min(f,c));if(!fi) dis[v]=-1;sum+=fi,f-=fi,get<1>(e[i])-=fi,get<1>(e[i^1])+=fi;}return sum;}LL solve(){LL ans=0;while(bfs()){for(int i=1;i<=n;i++) cur[i]=head[i];ans+=dfs(s,linf);}return ans;}
};
FLOW fw;
int main(){int n,m,s,t; read(n),read(m),read(s),read(t);fw.init(n,s,t);for(int i=1;i<=m;i++){int u,v,c; read(u),read(v),read(c);fw.add_edge(u,v,c);}printf("%lld",fw.solve());return 0;
}
//^o^
最小费用最大流
每条边有单位流量的费用，保证流量最大的同时，最小的费用。
把 BFS 换成 SPFA 即可。
参考实现代码
#include<bits/stdc++.h>
#define fst first
#define sec second
#define mkp(a,b) make_pair(a,b)
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int maxn=5010,maxm=4e6+10,inf=1e9+1;
const LL linf=1e18+1;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
struct FLOW{int head[maxn],nxt[maxm],mp_cnt;tuple<int,LL,LL> e[maxm];int n,s,t;LL maxf,minc;void init(int ni,int si,int ti){n=ni,s=si,t=ti,maxf=minc=0;fill(head+1,head+ni+1,-1),mp_cnt=-1;}void add_edge(int u,int v,LL f,LL c){e[++mp_cnt]=make_tuple(v,f,c);nxt[mp_cnt]=head[u],head[u]=mp_cnt;e[++mp_cnt]=make_tuple(u,0,-c);nxt[mp_cnt]=head[v],head[v]=mp_cnt;}bool ins[maxn];int cur[maxn];LL dis[maxn];bool SPFA(){fill(dis+1,dis+n+1,linf),fill(ins+1,ins+n+1,0);queue<int> q; q.push(s); ins[s]=1,dis[s]=0;while(!q.empty()){int u=q.front(); q.pop(),ins[u]=0;for(int i=head[u];~i;i=nxt[i]){int v; LL f,c; tie(v,f,c)=e[i];if((!f)||dis[u]+c>=dis[v]) continue;dis[v]=dis[u]+c; if(!ins[v]) { q.push(v),ins[v]=1; }}}return dis[t]^linf;}LL dfs(int u,LL lst){if(u==t) return lst;ins[u]=1; LL sum=0;for(int i=cur[u];(~i)&&lst;i=nxt[i]){cur[u]=i;int v; LL f,c; tie(v,f,c)=e[i];if((!f)||dis[u]+c!=dis[v]||ins[v]) continue;LL p=dfs(v,min(lst,f));if(!p) dis[v]=-linf;sum+=p,get<1>(e[i])-=p,get<1>(e[i^1])+=p,lst-=p;minc+=p*c;}ins[u]=0;return sum;}void work(){while(SPFA()){for(int i=1;i<=n;i++) cur[i]=head[i],ins[i]=0;maxf+=dfs(s,linf);}}
};
FLOW fw;
int n,m,s,t;
int main(){read(n),read(m),read(s),read(t);fw.init(n,s,t); for(int i=1;i<=m;i++){int u,v,f,c; read(u),read(v),read(f),read(c);fw.add_edge(u,v,f,c);}fw.work();printf("%lld %lld",fw.maxf,fw.minc);return 0;
}
//^o^
无原汇上下界的网络流
每条边都有一个流量下界和流量上界，无源汇就是说每个点都满足流入量等于流出量。
假设每条边的流量设置为其流量下界，然后会发现有些点并没有流量平衡，统计出每个点缺失或多余的流量。然后以每条边的最大流量减去最小流量作为流量限制，新建源汇点 S 和 T，原先缺失流量的点向 T 连边，流量限制为缺失的流量，原先多余流量的点从 S 连向它，流量限制为多余的流量，跑最大流。相当于把流量分成了两部分，一部份是下界流量，必须有，但是会有缺失或多余，一部份是差量网络，需要补足下界网络的流量缺失和多余，于是我们就用新的源汇点来模拟这种缺失和多余。注意上文中加粗的部分，这里容易搞反，不是说缺失了就要向 T 连边补足，而是要模拟这种缺失，以达到在两个部分的网络流重新加在一起的时候能够保持流量平衡，多余的时候同理。所以在检查该网络流是否可行是，只需要查验新补上的边是否全部流满就可以了，真实流量就是差量网络中的流量加上下界流量。
梳理一下连边：
- 原图中 \((u,v,l,r)\) 的边，连边 \((u,v,r-l)\)。
- 若点 \(u\) 在下界网络中多向外流了 \(f\) 的流量，则连边 \((u,t,f)\)。若少流入了 \(f\) 的流量，则连边 \((s,u,f)\)。
有源汇上下界网络流
由汇点向源点之间连一条容量为 \(\inf\) 的边，这样变成了无原汇上下界的网络流，同理求解即可。
注意：如上方法跑出的都是上下界网络流中的最小可行流，如需最大流，去除补上的边，算出每条边的剩余流量，再跑最大流。
带有负费用圈的网络流
对于一条负费用的边，直接使其满流，并加入一条容量相同，费用相反，方向相反的边用于退流，强制满流可以用上下界相同网络流实现。
一些关于网络流的常见思路和套路
最小割
最小割，就是在图中去除边，使得 S 和 T 不连通，需要去除边的最小边权和。
流量设为边权，最小割 = 最大流。
总点数 - 最大匹配 = 最小链覆盖 = 最大独立集
最大匹配是指在一个图中，包含边数最多的匹配，且每个顶点至多被一条边覆盖。
二分图的最大匹配，做法为源点连向左边的点，右边的点连向汇点，所有边的流量均为 1，跑最大流。
有向图的最大匹配，做法为把一个点拆成入度和出度，再连成二分图后跑最大流。（入度点不用连出度点）
最小链覆盖：覆盖所有点的最少的链的数量。
最大独立集：在图中取点，使得其中任意一个点都不能到达其他点，这样能取得最多的点得数量。
棋盘上的放置问题
通常要找出两类格子，一条有向边表示选了这个格子就不能选另一个格子，于是就得到一张二分图。源点连向左边的点，右边的点连向汇点，这些边权均为 1，表示切割代价为 1，中间的边边权为 \(\inf\)，表示不能切割，找到最小割模型。