最小割树

其实不是很难的东西。

最小割树的定义：树边 \((u,v)\) 的边权是 \(u,v\) 的最小割，删掉 \((u,v)\) 之后树被分成的两部分是一个最小割方案中点被分成的两部分，且任意两点 \(S,T\) 之间的最小割等于 \(S,T\) 在最小割树路径上的最小值。

构造严格的最小割树是很困难的事情，OI中一般构造的是等价流树，即不满足第二个条件的树。

我们考虑分治来构造，从当前点集中任意挑出两点 \(x,y\)，跑最小割，在最小割树上连接 \((x,y)\)，此时图被这组割分成了两部分，我们递归两部分构建，容易发现构造出来的树是一棵等价流树。

除去烦人的 dinic，构造代码很简单，只需要注意由于我们求的是原图上的答案，每次最小割要在整张图而非点集上跑：

inline void color(int now) {
	vis[now] = 1;
	for (int i = ed[now].head; i; i = ed[i].nxt) {
		int v = ed[i].to;
		if (vis[v] || ed[i].val == 0) continue;
		color(v);
	}
}

inline void calc(vector<int> S) {
	if (S.size() <= 1) return ;
	int x = S[0], y = S[1];
	for (int i = 0; i <= en; ++i) ed[i].val = ed[i].org;
	for (int i = 1; i <= n; ++i) vis[i] = 0;
	s = x; t = y; int val = dinic();
	nxt[x].push_back(make_pair(y, val));
	nxt[y].push_back(make_pair(x, val));
	ans[x][y] = ans[y][x] = val;
	vector<int> s1, s2;
	color(s);
	for (auto i : S)
		vis[i] ? s1.push_back(i) : s2.push_back(i);
	calc(s1); calc(s2);
	for (auto i : s1)
		for (auto j : s2)
			ans[i][j] = ans[j][i] = min_(min_(ans[i][x], ans[y][j]), ans[x][y]);
}

我们要跑 \(\Theta(n)\) 次网络流，复杂度是 \(\Theta(n\times \texttt{dinic})\)

例题（CF343E）：

设 \(\lambda(x,y)\) 表示 \(x,y\) 间的最小割，找一个排列 \(p\)，最大化 \(\sum \lambda(p_i,p_{i+1})\)

建立最小割树，答案的是所有边权和。构造考虑找到树上边权最小的边，它一定会会被算到，递归两边即可。容易发现无法构造比它更大的答案。