题解 【P5934 [清华集训2012]最小生成树】

$\texttt{Description}$

给你一个 $n$ 个点，$m$ 条边的图，请问至少删除原图上的多少条边，才能使得加入一条从 $u$ 到 $v$ 边权为 $L$ 的边后，该边同时在任意一颗最小生成树和最大生成树上。

$ \texttt{Data Range:}1\le n\le 2\times 10^4,1\le m\le 2\times 10^5$

$\texttt{Solution}$

根据 kruskal 算法的原理，一条边权为 $L$ 的边在最小生成树上，必须有将所有边权 $<L$ 的边加入后，$u$ 和 $v$ 仍然不连通。

那么问题转化为，只考虑边权 $<L$ 的情况下，需要删除多少条的边，使得 $u,v$ 不连通。就是个最小割问题了。最大生成树同理。

解释一下为什么没有取到等号，因为题目只要求出现在任意一颗 MST 上，而对于 kruskal 而言，排序的时候边权相同的边之间的顺序可以随意（而且如果不能随意，就不能使用 sort 这种不稳定的排序了）。所以为了满足题目的要求，在边权为 $L$ 的，两个端点仍未连通的边中，我们选择题目让我们新加的那条边。

虽然流量为 $1$ 的图上 Dinic 有优势，但是不管常数多小的 Dinic 仍然被 ISAP 吊起来打

不过大多数时候 EK 和 ISAP 差不多

$\texttt{Code}$

#include <cstdio>
#include <queue>
#include <cstring>

const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, cap;
} e[800005];
int head[20005], cur[20005], num[20005], dep[20005], from[200005], to[200005], val[200005];
int tot = 1, s, t, n, m;
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap) {
	e[++ tot].to = v, e[tot].cap = cap, e[tot].nxt = head[u], head[u] = tot;
}

void bfs() {
	memset(num, 0, sizeof num);
	memset(dep, 0, sizeof dep);
	memcpy(cur, head, sizeof cur);
	Q.push(t);
	num[dep[t] = 1] = 1;
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		for (int i(head[u]); i; i = e[i].nxt)
			if (!dep[e[i].to]) ++ num[dep[e[i].to] = dep[u] + 1], Q.push(e[i].to);
	}
}

int dfs(const int u, const int flow) {
	if (u == t) return flow;
	int used(0), tmp(0);
	for (int i(head[u]); i; i = e[i].nxt) {
		cur[u] = i;
		if (dep[u] - 1 == dep[e[i].to] && e[i].cap) {
			if (tmp = dfs(e[i].to, min(e[i].cap, flow - used)))
				e[i].cap -= tmp, e[i ^ 1].cap += tmp, used += tmp;
			if (used == flow) return used;
		}
	}
	if (!(-- num[dep[u]])) dep[s] = n + 1;
	++ num[++ dep[u]];
	return used;
}

int ISAP() {
	int Maxflow(0);
	bfs();
	while (dep[s] && dep[s] <= n) Maxflow += dfs(s, INF);
	return Maxflow;
}

int main() {
	int ans(0), L;
	scanf("%d%d", &n, &m);
	for (int i(1); i <= m; ++ i) scanf("%d%d%d", from + i, to + i, val + i);
	scanf("%d%d%d", &s, &t, &L);
	for (int i(1); i <= m; ++ i)
		if (val[i] < L) AddEdge(from[i], to[i], 1), AddEdge(to[i], from[i], 1);
	ans = ISAP();
	memset(head, 0, sizeof head);
	tot = 1;
	for (int i(1); i <= m; ++ i)
		if (val[i] > L) AddEdge(from[i], to[i], 1), AddEdge(to[i], from[i], 1);
	printf("%d\n", ans + ISAP());
	return 0;
}