网络流总结
最大流
定义
一张图，给定源点、汇点，保证源点无入边，汇点无出边，为每条边安排一个流量，最小为 $0$ ，最大为给定的参数，保证除源点、汇点以外所有点流恒等性，也就是入边流量之和等于出边流量之和 ，最大化源点所有出边的流量和。
经典算法
Dinic
算法流程
进行 bfs 分层后，我们规定一条边只能从层数 $i$ 流向 层数 $i+1$ ，其余边忽略，然后 dfs 出最大的增广流，这里的增广流不单指一条链，而可以是多条链，然后合并到图中，重复直到找不出增广流。
另外，增广后建反边，容量为当前增广路流量，代表反悔。
时空复杂度
当前弧优化
很明显，在进行 dfs 时，我们只用从上次 dfs 结束的点开始，这是因为除开最后一个节点，其余节点都已经到达最大流状态（阻塞），不用进行 dfs 。
普通情况
先分析单轮时间复杂度。
dfs 过程中不可能有环。（最大流不可能有环，不然你去了环不一样的？）
所以每条增广路的时间为 $\mathcal{O}(n)$
同时一条增广路（与增广流区分）能使一条边满流（流量 $=$ 容量）。
很明显啊，如果一条边都不满流，那流量为什么都不 $+1$ 达到更大呢？
所以增广路数量为 $\mathcal{O}(m)$
单次时间复杂度 $\mathcal{O}(nm)$
tips：常见伪证：每个点每条出边最多遍历 $\mathcal{O}(m)$ 次，所以时间复杂度即为 $\mathcal{O}(nm)$ 。
bug：我们从上次结束的点开始，所以上次结束的点实际遍历了 $2$ 次。
然后分析增广轮数。
不太会。。。
去 最大流 - OI Wiki 吧。
特殊情况
所以为什么用 Dinic 呢？时间复杂度照样 $\mathcal{O}(n^2m)$ ，慢得要死。
实际上，Dinic 的均摊时间复杂度并不大，而且卡 Dinic 图的性质比较吊，实际应用中很难构造，一句话概括：~SPFA 。
这个东西比SPFA靠谱，我们分析一些特殊情况
单位容量
也就是说容量要么 $0$ 要么为同一个数，在这种情况单轮增广因为每次都能使所有的边满流，所以每条边只能增广一次，所以时间复杂度为 $\mathcal{O}(m)$ 。
我们现在来讨论增广轮数
也不太会。。。
时间复杂度 $\mathcal{O}(n\min(\sqrt n,m^{\frac 2 3})$。
并且如果所有非源点汇点的入度和出度都为 $1$ ，时间复杂度为 $\mathcal{O}(n^{\frac 1 2}m)$ 。
实际情况一般都用 Dinic ，因为这个不容易被卡。
代码实现：
int x[105];
int y[105];
int fir[505];
int nxt[5000005];
int v[5000005];
int now;
int s,t;
int can[5000005];
int used[5000005];
void add(int x,int y,int z){
v[++now]=y;
nxt[now]=fir[x];
fir[x]=now;
can[now]=z;
used[now]=0;
return ;
}
bool ignore[5000005];
namespace Dinic{
std::queue<int>qu;
int nfir[100005];
int dep[100005];
bool bfs(int now){
for(int i=1;i<=t;i++){
dep[i]=0;
}
dep[now]=1;
qu.push(now);
while(qu.size()>0){
int tt=qu.front();
qu.pop();
for(int i=fir[tt];i!=-1;i=nxt[i]){
if(dep[v[i]]||can[i]==used[i]){
continue;
}
dep[v[i]]=dep[tt]+1;
qu.push(v[i]);
}
}
return dep[t];
}
int dfs(int now,int flow){
if(flow==0||now==t){
return flow;
}
int nflow=0;
for(int &i=nfir[now];i!=-1;i=nxt[i]){
if(dep[v[i]]!=dep[now]+1||can[i]==used[i]){
continue;
}
int tt=dfs(v[i],std::min(flow-nflow,can[i]-used[i]));
if(tt==0){
continue;
}
nflow+=tt;
used[i]+=tt;
used[i^1]-=tt;
if(nflow==flow){
return nflow;
}
}
return nflow;
}
int solve(int ans=0){
while(bfs(s)){
for(int i=1;i<=t;i++){
nfir[i]=fir[i];
}
ans+=dfs(s,0x3f3f3f3f);
}
return ans;
}
};最小割
关于割的严谨定义参考最小割 - OI Wiki，就不复制了。
你需要划分网络中的点，源点汇点必须分属两个集合。
割的容量定义为所有从一个集合到另一个集合的边的容量之和。
最小割即最小化割的容量。
最大流即最小割。
边满流意味此边被割。
费用流
PD原始对偶算法
费用流的思路都是贪心找最小的费用流加上，不过因为边权可能为负，我们的 SPFA ，他死了，我们可否像 Johnson 全源最短路一样把边权搞成正的。
像 Johnson 一样把边权改成 $w+h_u+h_v$ 。
图形态变了怎么办？
设增广后源点到 $i$ 的路径为 $d_i$ ，令 $h_i=h_i+d_i$ 即可。
$(i,j)$ 若被增广，则会多一些 $(j,i)$ 的边，有 $d_i+(w(i,j)+h_i-h_j)=d_j$ ，稍作变形发现边权非负。
若未被增广，增广前即满足上式，可推出 $h_i+d_i$ 非负。
证毕，边权皆非负，可用Dij求解最短路。
namespace mcflow{
bool vis[5000005];
int h[5000005];
int dis[5000005];
int pre[5000005];
int usedge[5000005];
class node{
public:
int id,data;
node(int x,int y){
id=x;
data=y;
return ;
}
};
bool operator < (node a,node b){
return a.data>b.data;
}
void spfa(){
std::queue<int>qu;
for(int i=1;i<=t;i++){
vis[i]=0;
h[i]=0x3f3f3f3f3f3f3f;
}
h[s]=0;
vis[s]=1;
qu.push(s);
while(qu.size()>0){
int tp=qu.front();
qu.pop();
vis[tp]=0;
for(int i=fir[tp];i!=-1;i=nxt[i]){
if(can[i]!=used[i]&&h[v[i]]>h[tp]+cost[i]){
h[v[i]]=h[tp]+cost[i];
if(vis[v[i]]==0){
vis[v[i]]=1;
qu.push(v[i]);
}
}
}
}
return ;
}
bool dij(){
std::priority_queue<node>qu;
for(int i=1;i<=t;i++){
dis[i]=0x3f3f3f3f3f3f3f;
vis[i]=0;
pre[i]=0;
}
dis[s]=0;
qu.push(node(s,0));
while(qu.size()>0){
node temp=qu.top();
qu.pop();
if(vis[temp.id]){
continue;
}
vis[temp.id]=1;
for(int i=fir[temp.id];i!=-1;i=nxt[i]){
int edge=cost[i]+h[temp.id]-h[v[i]];
if(can[i]!=used[i]&&dis[v[i]]>dis[temp.id]+edge){
dis[v[i]]=dis[temp.id]+edge;
usedge[v[i]]=i;
pre[v[i]]=temp.id;
if(vis[v[i]]==0){
qu.push(node(v[i],dis[v[i]]));
}
}
}
}
return dis[t]!=0x3f3f3f3f3f3f3f;
}
int ans(int &anss){
spfa();
int ans=0;
anss=0;
while(dij()){
for(int i=1;i<=t;i++){
h[i]+=dis[i];
}
int minf=0x3f3f3f3f3f3f3f;
for(int i=t;i!=s;i=pre[i]){
minf=std::min(minf,can[usedge[i]]-used[usedge[i]]);
}
for(int i=t;i!=s;i=pre[i]){
used[usedge[i]]+=minf;
used[usedge[i]^1]-=minf;
}
anss+=minf;
ans+=minf*h[t];
}
return ans;
}
};