全机房就我一个还不会网络流了。
下面我整理一下网络流的基本概念，辅助自己理解。
首先关于网络流的定义。形式化地说，网络流是一张图\(G(V,E)\)（有时也指这张图的一个状态），满足以下性质：
1.流量上限：对于任意一条边\(e\in E\)，存在一个属性\(c_{e}\)，定义它为这条边的流量上限。
2.流量受限：对于任意一条边\(e\in E\)，存在一个属性\(0\le f_{e}\le c_{e}\)，定义它为这条边当前的流量。
3.流量守恒：对于任意一个点\(v\)，满足：\(\sum_{i\in{a|a_{v}=v,a\in E}}f_{i}=\sum_{j\in{b|b_{u}=v,b\in E}}f_{j}\)
4.源点汇点：存在两个点，分别叫做源点和汇点。其中，源点能够流出无穷多流量，而汇点能够流入无穷多流量。
若一个网络流的某一个状态满足上述所有性质，我们就称这个状态是合法的。
我们定义，对于一张网络流，使得它从源点流向汇点的流量最大的状态，为最大流。
求解最大流，就是指，求解最大流的状态。
为了辅助求解这个问题，我们可以考虑对于每一条边\(e\)都建一条反边\(e’\)。它的方向与原边相反。且\(f_{e’}=f_{e}\)
那么，所有的反边构成了另一张图\(G(E’,V)\)，它描述的是它的原边已经走过的流量。
将一张图上的每一条边都只保留它的当前剩余流量\(f_{e}\)，这张图可以被认为是对原图的流量空余的描述。故而我们称这张图为残余网络。
我们定义增广路径，指的是，在包括反边的残余网络的一条路径上面的一条路径，使得路径上的每一条原边都是不满的，且路径上每一条反边都是非空的。
对于关于这条路径上的所有原边，将其流量上限减去当前流量的值减去最小值，再对路径上每一条反边的当前流量值取最小值，再对两个最小值取最小值。
然后将所有原边的流量加上这个最小值，并将每一条反边的流量减去这个最小值（对应的反/原边同时减/加相应值）。 我们称这样一个操作为增广，称操作中减少反边流量的子操作为撤销。
如果当前图不是处于最大流的状态，那么一定可以找到一个增广路；如果当前图属于最大流的状态，那么一定没有增广路。
我们朴素地考虑如何利用增广来取得最大路径。如果我们每一次都暴力地寻找整个网络上的一条可行增广路并且增广（这似乎被称作F-F算法），在很糟糕的情况下，可能会出现很多次反复地增广而只增加很少的流量的情况。
在上诉的算法中，可能存在一种情况，就是，一条边被反复地增广-撤销多次。这样无形中增大了很多复杂度。
我们考虑上诉的情况是如何产生的。很显然，经过一次撤销操作之后，当前的路径的长度减少了一条边，而原来经过那条边的那些流量所在的路径上的长度也减少了一条边。
那么反复地增广-撤销操作的一个很大的原因，便是，第一次增广到这条边的时候的路径经过的边数太多。
如果每一次搜索增广路径的时候，都尽可能搜索边数尽可能少的一条边，那么便可以使得增广-撤销操作尽可能少。（这似乎被称作E-K算法）
上述的算法都可以被称作是朴素的算法。但复杂度最坏情况下可能会被卡到非常大，大概是\(O(n\times m^2)\)级。
下面是一个对于这个算法的正确性的感性证明。
我们首先证明，每一次增广之后，图上流过的流量都增多。
对于一次增广，当我们流过一条边的时候，流过的流量存在两种情况：
1.这些流量走过的是反边。
2.这些流量走过的是原边。
对于流过原边的流量，很显然无论如何可以流的，并且会将原图的状况改进得更优。
而对于流过反边的流量，可以视为将这些流量还原，然后原来流到这条边的那些流量，现在从当前路径流过这条边之后的那部分流走；而当前流到这条边的流量，则从之前流过这条边的那些流量的后半部分流走。
所以，每一次增广，总是会导向一个合法状态。
又因为，每一次增广之后，源点都会流出更多的流量，汇点都会收到更多的流量，所以整张图流过的流量增加了。
然后我们考虑证明，当不再能增广的时候，图上处于最大流的状态。
当走过一条边的时候，我们事实上完成了一次「反悔」，也就是指，让之前从这里走的一些流量往另一个方向走了。
如果，不再可以增广，这就意味着，无论反悔到什么程度、无论怎么改变之前已有的流量的路径，都无法找到一条新的路径使得流量可以通过。
即，哪怕是在反悔最多的情况下，也找不到一条能够产生更多流量的路径。
那么，我们就可以断言这个状态已经是最大流的状态了。
回到算法本身上。下面我们考虑优化这个朴素算法。\(O(n\times m^2)\)的复杂度显然是不可接受的。
Dinic算法就是一种对上述朴素算法的优化。
我们考虑一种被称为「多路增广」的操作。这种操作也是Dinic的核心。
对于每一次多路增广，我们首先将整张图dfs一遍，预处理出深度小于源汇距离的所有节点的深度。这样我们得到了一张分层图。
然后我们从源点开始进行一种特殊的DFS——每一次访问的节点的深度必须比前一个节点深，并且搜索经过的边必须是可以增广的边。
当我们搜索到汇点的时候，便开始沿着来路回溯，直到回溯到第一个「来路仍然可以继续增广」并且「连着其他还可以被继续增广的边」的节点为止，然后继续向下搜索。
如果回溯到了源点，多路增广结束。
然后，对剩下可以走的部分，重新计算深度，并重跑增广，直到不能再增广为止。
对于每一次多路增广，我们可以以\(O(nm)\)的复杂度遍历完成对某一个特定深度的所有增广操作。 而多路增广显然是最多只会被执行\(n\)次的。故而这么做的复杂度是\(O(n^2+m)\)的。
我们就得到了一个相对较优的算法。
#include<iostream>
#include<cstdio>
#include<queue>
const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
return A<B?A:B;
}
struct ee{
int v;
int w;
int nxt;
}e[200005];
int h[10005],et=-1;
int n,m,s,t,ans=0,dep[10005],nw[10005];
inline void add(int U,int V,int W){
e[++et]=(ee){V,W,h[U]};
h[U]=et;
}
std::queue<int> q;
inline bool bfs(){
for(int i=1;i<=n;++i){
dep[i]=INF;
nw[i]=h[i];
}
while(!q.empty()){
q.pop();
}
dep[s]=0;
q.push(s);
int p;
while(!q.empty()){
p=q.front();
q.pop();
for(int i=h[p];i>=0;i=e[i].nxt){
if(dep[e[i].v]==INF&&e[i].w){
dep[e[i].v]=dep[p]+1;
q.push(e[i].v);
}
}
}
return dep[t]<INF;
}
inline int dfs(int X,int V){
if((V<=0)||(X==t)){
return V;
}
int cnt=0,val;
for(int i=nw[X];i>=0;i=e[i].nxt){
nw[X]=i;
if(dep[e[i].v]==dep[X]+1){
val=dfs(e[i].v,Min(V,e[i].w));
if(val){
cnt+=val;
V-=val;
e[i].w-=val;
e[i^1].w+=val;
if(V<=0){
break;
}
}
}
}
return cnt;
}
void init(){
scanf("%d%d%d%d",&n,&m,&s,&t);
int u,v,w;
for(int i=1;i<=n;++i){
h[i]=-1;
}
for(int i=1;i<=m;++i){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
while(bfs()){
ans+=dfs(s,INF);
//注意应当填写起始点。
}
printf("%d\n",ans);
}
int main(){
init();
return 0;
}