JZTXT

2023 CSP-S 备战

发布时间 2023-09-29 10:51:11作者: cqbz_dxm

2023 CSP-S 备战

日常犯智

9.29

  1. Dinic 中，如果 rest 为 \(0\)，直接终止循环。

    int dinic (int u, int flow) {
	if (u == T) return flow;
	int rest = flow;
	for (int i = now[u]; i && rest; i = edge[i].nxt) {  //rest
		now[u] = i;
		int v = edge[i].v, c = edge[i].c;
		if (c > 0 && d[v] == d[u] + 1) {
			int k = dinic(v, min(rest, c));
			if (!k) d[v] = 0;
			rest -= k, edge[i].c -= k, edge[i^1].c += k;
		}
	}
	return flow - rest;
}