LCT 优化 Dinic

我觉得这东西有必要记一下，因为光是看 PPT 很难自己写出代码……具体步骤相关啥都没写。

另外学这个东西也不是很必要……

Solution

我们需要一个维护最小值、最小值编号，支持区间加的 LCT。需要支持以下操作：

• \(find\_root(u)\)
• \(link(u,v)\)
• \(cut(u,v)\)
• \(find\_min(v)\)
• \(add(u,value)\)

（注意到只需要实现 access）

首先 BFS 步骤不变，注意从 \(t\) 倒着来。得到分层图 \(G_L\) 后，通过 DFS 增广，增广步骤如下：

1. 对 \(G_L\) 上的每一个点建立一棵恰好包含自己一个点的树。
2. 设跟踪的节点为 \(v\)，初始置 \(v\) 为源点 \(s\)。选择一条出边 \((v,u)\)，将 \(v\) 所在树连接到 \(u\) 上，设 \(v\) 的权值为出边的边权，最后将 \(v\) 移动到当前树的根。
3. 若 \(v\) 没有出边，那么回溯到 \(u\)，删除 \((u,v)\)，如果该边是树边，则断开树上相应边。
4. 如果 \(v=t\)，找到树上对应的 \(s\sim t\) 路径，将总流量加上 \(find\_min(s)\)，再将路径上所有点的权值减去增广流量，删除路径上的所有零边。重新置 \(v\) 为源点 \(s\)，重复步骤 3。
5. 如果源点 \(s\) 没有出边，所有增广结束，进行下一次分层。

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
#define mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
const int N = 1e5 + 10, M = 1e5 + 10, INF = 2147483647;
int n, m, s, t;
struct Edge {
	int t, n, w, del;
} e[M];
int tot = 1, h[N], cur[N];
void add(int u, int v, int w) {
	e[++tot] = (Edge){v, h[u], w, 0}, h[u] = cur[u] = tot;
}
void eadd(int u, int v, int w) {
	add(u, v, w), add(v, u, 0);
}

struct LCT {
	int ch[N][2], fa[N], mn[N], mnid[N], add[N], val[N], id[N], lef[N];
	LCT() {
		mem(ch), mem(fa), mem(add), mem(id);
	}
  #define get(u) (u == ch[fa[u]][1])
  #define nrt(u) (u == ch[fa[u]][0] || u == ch[fa[u]][1])
	void up(int u) {
		mn[u] = min({mn[ch[u][0]], val[u], mn[ch[u][1]]});
		if (mn[u] == mn[ch[u][0]]) mnid[u] = mnid[ch[u][0]];
		else if (mn[u] == val[u]) mnid[u] = u;
		else mnid[u] = mnid[ch[u][1]];
		if (ch[u][0]) lef[u] = lef[ch[u][0]];
		else lef[u] = u;
	}
	void Add(int u, int v) {
		if (u) mn[u] += v, add[u] += v, val[u] += v, e[id[u]].w += v, e[id[u] ^ 1].w -= v;
	}
	void down(int u) {
		if (add[u]) Add(ch[u][0], add[u]), Add(ch[u][1], add[u]), add[u] = 0;
	}
	void Down(int u) {
		if (nrt(u)) Down(fa[u]);
		down(u);
	}
	void rot(int u) {
		int f = fa[u], g = fa[f], k = get(u);
		if (nrt(f)) ch[g][get(f)] = u;
		ch[f][k] = ch[u][!k];
		if (ch[u][!k]) fa[ch[u][!k]] = f;
		ch[u][!k] = f, fa[f] = u, fa[u] = g, up(f), up(u);
	}
	void splay(int u) {
		for (Down(u); nrt(u); rot(u)) if (nrt(fa[u])) rot(get(u) == get(fa[u]) ? fa[u] : u);
	}
	void access(int u) {
		for (int v = 0; u; v = u, u = fa[u]) 
			splay(u), ch[u][1] = v, up(u);
	}
	int find(int u) {
		return access(u), splay(u), lef[u];
	}
	void Del0(int u) {
		for (down(u); ch[u][1] && !mn[ch[u][1]]; )
			u = mnid[ch[u][1]], splay(u), fa[ch[u][0]] = 0, ch[u][0] = 0, up(u);
	}
	void cut(int u) {
		access(u), splay(u), fa[ch[u][0]] = 0, ch[u][0] = 0, up(u);
	}
  #undef get
  #undef nrt
} lct;

void init() {
	rep(i, 1, n) lct.splay(i); // 释放标记
	lct = LCT();
	rep(i, 0, n) lct.mnid[i] = lct.lef[i] = i, lct.mn[i] = lct.val[i] = INF;
}

int res, dis[N], que[N];
int bfs() {
	memset(dis, 0, sizeof(dis));
	init();
	dis[que[1] = t] = 1;
	for (int L = 1, R = 1; L <= R; ++L)
		for (int i = h[que[L]]; i; i = e[i].n) {
			e[i].del = e[i ^ 1].del = 0;
			if (e[i ^ 1].w && !dis[e[i].t])
				dis[que[++R] = e[i].t] = dis[que[L]] + 1;
		}
	if (!dis[s]) return 0;
	memcpy(cur, h, sizeof(cur));
	return 1;
}

int dfs(int u) {
	if (u == t) {
		lct.access(s), lct.splay(t);
		int ret = lct.mn[t];
		res += ret;
		lct.add[t] -= ret;
		lct.Del0(t);
		return 1;
	}
	for (int &i = cur[u]; i; i = e[i].n) {
		int v = e[i].t;
		if (e[i].w && dis[v] == dis[u] - 1 && !e[i].del) {
			lct.splay(u), lct.fa[u] = v, lct.val[u] = e[i].w, lct.id[u] = i, lct.up(u);
			if (dfs(lct.find(u))) return 1;
		}
	}
	for (int i = h[u]; i; i = e[i].n) {
		int v = e[i].t;
		if (dis[v] == dis[u] + 1) {
			if (lct.find(v) == u)
				lct.cut(v);
			e[i ^ 1].del = 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m >> s >> t;
	rep(i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		eadd(u, v, w);
	}
	while (bfs()) 
		while (dfs(lct.find(s)));
	cout << res << '\n';
	return 0;
}