前面花了很长时间弄明白了压入-重标记的各种方法，结果号称是O(V3)的算法测demo的时候居然TLE了一个点，看了题解发现所有人都是用Dinic算法写的，但它的复杂度O(V2E)明显高于前者，具体是怎么回事我也不太清楚。。。但是Dinic算法相对来说要好理解多了。
经过证明（然而并不知道怎么证明），在残余网络中增广路中的最短路，一定是对答案贡献最大的（即对求解时间贡献最大）增广路。
算法显而易见了，每次找增广路之前先bfs一遍得出残余网络中源点到每个点的最短路径（每条边长度固定为1），得到一张“层次图”，根据层次图来找最优增广路（每个点只能向等级恰好比它多1的点流）
1 #include<iostream>
2 #include<iomanip>
3 #include<cstdio>
4 #include<map>
5 #include<queue>
6 #include<algorithm>
7 #include<ctime>
8 #include<cstring>
9 #include<cstdlib>
10 #include<climits>
11 #include<cmath>
12 #include<vector>
13 using namespace std;
14 #define rep(i,a,b) for(int i=a;i<=b;i++)
15 #define dep(i,a,b) for(int i=a;i>=b;i--)
16 inline int read(){
17 int x=0;char ch=getchar();
18 while(ch<'0'||ch>'9')ch=getchar();
19 while(ch>='0'&&ch<='9'){
20 x=x*10+ch-'0';
21 ch=getchar();
22 }
23 return x;
24 }
25 const int MAXN=100010,MAXM=1000010;
26 int to[MAXM],next[MAXM],value[MAXM];
27 int level[MAXN],cnt=0,head[MAXN],s,t;
28 void _insert(int u,int v,int w){//链式前向星存图
29 to[cnt]=v;
30 value[cnt]=w;
31 next[cnt]=head[u];
32 head[u]=cnt++;
33 to[cnt]=u;
34 value[cnt]=0;
35 next[cnt]=head[v];
36 head[v]=cnt++;
37 }
38 bool bfs(){//构建层次图
39 memset(level,0,sizeof(level));
40 level[s]=1;//level[i]表示每个点的层次，即源点到其的最短路径，初始化源点的层次为1（这个无所谓，只要层次递增即可）
41 queue<int>q;
42 q.push(s);
43 while(!q.empty()){
44 int u=q.front();
45 q.pop();
46 for(int i=head[u];i!=-1;i=next[i]){
47 if(!level[to[i]]&&value[i]){
48 level[to[i]]=level[u]+1;
49 q.push(to[i]);
50 }
51 }
52 }
53 return level[t];//如果没有得出汇点的层次图，说明不存在增广路
54 }
55 int dfs(int u,int f){//u为当前节点，f为当前节点残余流量
56 if(!f||u==t)return f;
57 int rest=0;
58 for(int i=head[u];i!=-1;i=next[i]){
59 if(value[i]&&level[u]+1==level[to[i]]){//只能向层次恰好多1的点流入
60 int p=dfs(to[i],min(f,value[i]));//深搜寻找瓶颈
61 rest+=p;
62 f-=p;
63 value[i]-=p;
64 value[i^1]+=p;
65 }
66 }
67 return rest;
68 }
69 int main(){
70 int n=read(),m=read();
71 s=read();t=read();
72 memset(head,-1,sizeof(head));
73 rep(i,1,m){
74 int u=read(),v=read(),w=read();
75 _insert(u,v,w);
76 }
77 int ans=0;
78 while(bfs())ans+=dfs(s,INT_MAX);
79 cout<<ans<<endl;
80 return 0;
81 }