看向这样一份 Dinic 的实现：
#include<bits/stdc++.h>
using namespace std;
template<typename T> struct network {
const int n;
struct Arc {
int to; size_t rev; T w;
};
vector<vector<Arc>> e;
vector<int> lev,iter;
network(int n):n(n),lev(n),iter(n),e(n) {}
void add(int one,int ano,T cap) {
assert(1<=one && one<=n && 1<=ano && ano<=n);
e[one-1].push_back((Arc){ano-1,e[ano-1].size()+(one==ano),cap});
e[ano-1].push_back((Arc){one-1,e[one-1].size()-1,0});
}
bool bfs(int s,int t) {
queue<int,list<int>> q;
lev.assign(n,0);
for(q.push(s),lev[s]=1; q.size(); q.pop()) {
for(int now=q.front(),i=iter[now]=0,y; i<int(e[now].size()); ++i) {
if(now==t) return 1;
if(!lev[y=e[now][i].to] && e[now][i].w) q.push(y),lev[y]=lev[now]+1;
}
}
return lev[t];
}
T dfs(int now,T f,int t) {
if(now==t) return f;
T res=0,tt;
for(int& i=iter[now],y; i<int(e[now].size()); ++i) {
if(!f) break;
if(lev[y=e[now][i].to]==lev[now]+1 && e[now][i].w && (tt=dfs(y,min(f,e[now][i].w),t))) {
e[now][i].w-=tt; e[y][e[now][i].rev].w+=tt; f-=tt; res+=tt;
}
}
if(!res) lev[now]=0;
return res;
}
T get(int s,int t) {
assert(1<=s && s<=n && 1<=t && t<=n);
T res=0,f;
while(bfs(s-1,t-1)) {
if((f=dfs(s-1,numeric_limits<T>::max(),t-1))) res+=f;
else break;
}
return res;
}
};
signed main() {
int n,m,s,t;
scanf("%d %d %d %d",&n,&m,&s,&t);
network<long long> G(n);
for(int i=0,x,y,z; i<m; ++i) {
scanf("%d %d %d",&x,&y,&z);
G.add(x,y,z);
}
printf("%lld\n",G.get(s,t));
return 0;
};它在洛谷的最大流模板中取得了 sum runtime 440ms 的傻逼成绩，卡了我至少 4 题的常。
让我们来看看为什么这份实现跑得这么慢。
首先我使用了 std::size_t 来储存反向边的编号，然而实际上 std::size_t（std::vector<Type>::size_type） 在 64-bits 机器中是 long long unsigned int 的别名，也即，这个跑得比 int 慢多了。
其次是 std::queue<int, list<int>>，虽然 -Wallace- 在其 STL 博客中表示这将比 std::queue<int, deque<int>> 更快，但事实上至少在这里它跑得很慢……
最后是
for(int& i=iter[now],y; i<int(e[now].size()); ++i) {
if(!f) break;
if(lev[y=e[now][i].to]==lev[now]+1 && e[now][i].w && (tt=dfs(y,min(f,e[now][i].w),t))) {
e[now][i].w-=tt; e[y][e[now][i].rev].w+=tt; f-=tt; res+=tt;
}
}在经过实验对比（指，摸到 loj 势力上看了下为啥神户的板子跑这么快）后，我们惊讶的发现，下面代码所呈现的跑进了 50ms
for(int& i=iter[now],y; i<int(e[now].size()); ++i) {
if(lev[y=e[now][i].to]==lev[now]+1 && e[now][i].w && (tt=dfs(y,min(f,e[now][i].w),t))) {
e[now][i].w-=tt; e[y][e[now][i].rev].w+=tt; f-=tt; res+=tt;
if(!f) break;
}
}起初我以为是我的 $f$ 可能变成负数，但理论和事实都给了我两耳巴子。然后我怀疑是 std::vector<Type>::size() 的问题，但依然没有区别。
最后的怀疑是 ++i 的效率问题
for(int& i=iter[now],y; i<int(e[now].size()); ++i) {
if(lev[y=e[now][i].to]==lev[now]+1 && e[now][i].w && (tt=dfs(y,min(f,e[now][i].w),t))) {
e[now][i].w-=tt; e[y][e[now][i].rev].w+=tt; f-=tt; res+=tt;
if(!f) {++i; break;}
}
}飘成了 400ms，破案了？
不，再看
for(int i=iter[now],y; i<int(e[now].size()); ++i) {
iter[now]=i;
if(lev[y=e[now][i].to]==lev[now]+1 && e[now][i].w && (tt=dfs(y,min(f,e[now][i].w),t))) {
e[now][i].w-=tt; e[y][e[now][i].rev].w+=tt; f-=tt; res+=tt;
if(!f) {++i; break;}
}
}又跑进了 50ms，现在明了了，iter（std::vector<int>）的寻址太慢，并且剪枝剪掉的情况确实比较多，所以效率很低。