网络最大流Dinic算法 代码笔记

代码思路

主体部分：

构造分层图，找增广路
（即bfs和dfs）

辅助部分：

当前弧优化
（在bfs中进行重置，在dfs中进行更新）

整合：

首先是存图与主函数部分，通常还包括对问题的转换（也就是建图）。
剩下的就是bfs和dfs。

考虑bfs需要实现哪些功能：最主要地，它需要提供一个分层图，具体而言要得到一个dep[]数组，表示以s为起点，其余点的广搜深度；其次bfs还要提供增广路的有无，用于结束循环。
再考虑dfs需要实现的功能：无非就是统计流量，以及进行残留网络的更新（正减反加）。

简化部分：

日常struct存图

注意事项：

就算题面上是有向图，也要建双向边，所以记得\(\times 2\)。

原理（极简）

残留网络和残留网络的反向路径：Ford-Fulkerson

一个流是最大流，当且仅当其残留网络不包括增广路径

每次用BFS计算一条最短增广路： Edmonds-Karp

经过BFS结合DFS的优化： Dinic

代码注释

#include <bits/stdc++.h>
using namespace std;
#define int long long
// 不开long long见祖宗 

const int inf = 0x3f3f3f3f;
const int N = 505, M = 5005;
int n, m, s, t, cnt = 1, head[N], dep[N];
struct Edge{
	int u, v, w;
}e[M*2]; // 双向边,记得*2 

void add_edge(int u, int v, int w){
	e[++cnt] = (Edge){v, head[u], w};
	head[u] = cnt; // 普通建边 
}

int now[N], q[N], hd, tl; // 当前弧优化 bfs队列
bool bfs(){ // bool返回是否还有增广路 
//printf("qwq!\n");
	for(int i = 1; i <= n; i++) dep[i] = inf; // 清空
	dep[s] = 0, q[hd=tl=1] = s, now[s] = head[s]; 
	while(hd <= tl){ // 整体框架就是普通bfs 
		int u = q[hd++]; // 取出队首
		for(int i = head[u]; i; i = e[i].v){
			if(e[i].w > 0 && dep[e[i].u] == inf){
				// 还有容量剩余 且没有遍历过
				q[++tl] = e[i].u; // 就是，至少要记得加点…… 
				now[e[i].u] = head[e[i].u]; // 重置当前弧 
				dep[e[i].u] = dep[u]+1; // 记录分层
				if(e[i].u == t) return 1; // 抵达汇点 
			}
		} 
	} return 0; // 没有增广路 
}

int dfs(int u, int sum){ // 所在点 流量统计 
	if(u == t) return sum; // 抵达汇点返回
	int flow = 0; // 流量统计 
	for(int i = now[u]; i && sum; i = e[i].v){
		now[u] = i; // 更新当前弧 
		if(e[i].w > 0 && (dep[e[i].u] == dep[u]+1)){
			// 还有容量剩余 且通向下一层
			int k = dfs(e[i].u, min(sum, e[i].w));
			if(!k) dep[e[i].u] = inf; // 移除增广完的点
			e[i].w -= k, sum -= k; // 正向减
			e[i^1].w += k, flow += k; // 反向加 
		}
	} return flow;
} 

signed main(){
	scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
	for(int i = 1; i <= m; i++){
		int u, v, w; scanf("%lld%lld%lld", &u, &v, &w);
		add_edge(u, v, w); // 正向边流量初始为w
		add_edge(v, u, 0); // 反向边流量初始为0
		// 注意是双向边而非无向边,正反不能交换 
	} int ans = 0; // 统计答案
	while(bfs()) // 如果还有增广路
		ans += dfs(s, inf); // 更新答案
	printf("%lld\n", ans); 
	return 0;
}