TIOJ 2288：飛彈

TIOJ 2288：飛彈

題目大意：給你一張 $n$ 點 $m$ 邊的無向連通圖，請輸出 $i=1\sim n$，沒有第 $i$ 個點的最小生成樹，若圖不連通，輸出 $-1$。

解法：首先建出整張圖的最小生成樹，可以發現拔掉第 $i$ 個點後由小到大加入不在樹上的邊形成的樹會是新圖的最小生成樹。當要加入邊 $(u,v)$ 時，若 $u,v$ 為祖孫關係，那就讓深的點往上走並忽略已走過的點，若 $u,v$ 的 $\text{LCA}$ 是 $c$，那就走一遍 $u→c$ 與 $v→c$，最後再加 $c$ 的邊。

$\text{Code：}$

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 15e4 + 5;
const int M = 3e5 + 5;
const int H = __lg(N) + 1;

struct DSU {
	int n, cc;
	ll sum;
	vector<int> to, h, v;
	DSU() {}
	DSU(vector<int> vv) : v(vv) {
		n = v.size();
		cc = n;
		sum = 0;
		sort(v.begin(), v.end());
		to.resize(n);
		h.resize(n);
		iota(to.begin(), to.end(), 0);
	}
	int dsu(int x) {
		return x == to[x] ? x : (to[x] = dsu(to[x]));
	}
	bool Merge(int a, int b, int w) {
		a = dsu(lower_bound(v.begin(), v.end(), a) - v.begin());
		b = dsu(lower_bound(v.begin(), v.end(), b) - v.begin());
		if (a == b) return 0;
		if (h[a] < h[b]) swap(a, b);
		to[b] = a;
		h[a] += h[a] == h[b];
		cc--;
		sum += w;
		return 1;
	}
};

int n, m;
DSU ds[N];
bitset<M> is;
ll sum, ans[N];
int dto[N], dh[N];
vector<int> adj[N];
int to[N][H + 1], h[N];
tuple<int, int, int> e[M];

int dsu(int x) {
	return x == dto[x] ? x : (dto[x] = dsu(dto[x]));
}

bool Merge(int a, int b) {
	a = dsu(a), b = dsu(b);
	if (a == b) return 0;
	if (dh[a] < dh[b]) swap(a, b);
	dto[b] = a;
	dh[a] += dh[a] == dh[b];
	return 1;
}

void dfs(int pos, int fa) {
	for (int np : adj[pos]) if (np != fa) {
		h[np] = h[pos] + 1;
		to[np][0] = pos;
		dfs(np, pos);
	}
}

int jump(int pos, int k) {
	int cnt = 0;
	while (k) {
		if (k & 1) pos = to[pos][cnt];
		cnt++;
		k >>= 1;
	}
	return pos;
}

int lca(int a, int b) {
	if (h[a] < h[b]) swap(a, b);
	a = jump(a, h[a] - h[b]);
	if (a == b) return a;
	for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
		a = to[a][i];
		b = to[b][i];
	}
	return to[a][0];
}

void deal(int pos, int dep, int w) {
	while (h[pos] >= dep) {
		pos = dsu(pos);
		if (h[pos] < dep) break;
		ds[to[pos][0]].Merge(pos, to[to[pos][0]][0], w);
		dto[pos] = to[pos][0];
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		auto &[w, a, b] = e[i];
		cin >> a >> b >> w;
	}
	sort(e + 1, e + m + 1);
	iota(dto + 1, dto + n + 1, 1);
	for (int i = 1; i <= m; i++) {
		auto &[w, a, b] = e[i];
		if (Merge(a, b)) {
			sum += w;
			is[i] = 1;
			adj[a].emplace_back(b);
			adj[b].emplace_back(a);
		}
	}
	for (int i = 1; i <= n; i++) {
		ds[i] = DSU(adj[i]);
		ans[i] = sum;
	}
	for (int i = 1; i <= m; i++) if (is[i]) {
		auto &[w, a, b] = e[i];
		ans[a] -= w;
		ans[b] -= w;
	}
	h[1] = 1, dfs(1, 1);
	for (int j = 1; j <= H; j++) for (int i = 1; i <= n; i++) to[i][j] = to[to[i][j - 1]][j - 1];
	iota(dto + 1, dto + n + 1, 1);
	for (int i = 1; i <= m; i++) if (is[i] == 0) {
		auto &[w, a, b] = e[i];
		if (h[a] < h[b]) swap(a, b);
		if (jump(a, h[a] - h[b]) == b) {
			deal(a, h[b] + 2, w);
			continue;
		}
		int c = lca(a, b), ca = jump(a, h[a] - h[c] - 1), cb = jump(b, h[b] - h[c] - 1);
		deal(a, h[c] + 2, w);
		deal(b, h[c] + 2, w);
		ds[c].Merge(ca, cb, w);
	}
	for (int i = 1; i <= n; i++) cout << (ds[i].cc == 1 ? ans[i] + ds[i].sum : -1) << " \n"[i == n];
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！