【笔记】正确的当前弧优化

去年在 UOJ 上某道题网络流被卡了（UOJ ??，洛谷 ??），研究了一下发现是当前弧优化的原因。

当前弧优化应当这么写（原因在注释里）：

ll dfs(int u, ll flow) {
	if (u == T) return flow;
	ll rest = flow;
	for (int &i = nhd[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (e[i].f && d[v] == d[u] + 1) {
			ll k = dfs(v, min(rest, (ll)e[i].f));
			if (!k) d[v] = 0;
			rest -= k, e[i].f -= k, e[i ^ 1].f += k;
		}
		// rest 为 0 不代表不能继续走这条边扩展增广路，因为 rest 实际上是上一个点跑过来的流量。后面可能从另一条路径到达这条边，并且能通过这条边扩展，所以不能把 nhd[u] 设置为这条边的 nxt 导致以后都跳过这条边。
		if (!rest) break;
	}
	return flow - rest;
}

而不是蓝书上写的：

ll dfs(int u, ll flow) {
	if (u == T) return flow;
	ll rest = flow;
	for (int &i = nhd[u]; i && rest; i = e[i].nxt) {
		int v = e[i].v;
		if (e[i].f && d[v] == d[u] + 1) {
			ll k = dfs(v, min(rest, (ll)e[i].f));
			if (!k) d[v] = 0;
			rest -= k, e[i].f -= k, e[i ^ 1].f += k;
		}
	}
	return flow - rest;
}

注意 Dinic 必须加当前弧优化复杂度才是对的，即 \(O(n^2m)\)。if(!rest) break 和 if(!k) d[v] = 0 这两个优化可加可不加（虽然加了之后在洛谷上会快很多）。