Japan Alumni Group Spring Contest 2013 E - Minimum Spanning Tree

問題文 : Minimum Spanning Tree

概要 : 無向重み付きグラフ$G(V, E)$ が与えられる. すべての$e \in E$ について, $G - e$ の最小全域木の重さを求めよ.

$1 \leqq n \leqq 10^5$ (頂点数)
$1 \leqq m \leqq 2 \times 10^5$ (辺数)

解法 :

まず, $G$ の最小全域木の要素ではない辺を取り除いた時, その最小全域木の重さは元のグラフの最小全域木の重さと一致するため, 最小全域木を構成する$n - 1$ 本の辺についてだけ考えればいい.

このMST を適当な頂点を根として根付き木にして, 辺を取っていくことを考えると, 自身の部分木からもう一つの連結成分へ辺が伸びているもののうちコストが最小のものをとれば良いことが分かる. 最小のコストの辺はpriority_queue を使えばわかるが, これを併合するのはデータ構造をマージする一般的なテクを使えば良い. (小さいpriority_queue を大きいほうに併合する).

自分の子孫かどうかの判定はlowlink を使うとO(1) ででき, priority_queue に入る辺は高々$O(m)$ 本であるから, 全体の計算量は$O(m \log^2 m)$ となる.

しかしdfs でlowlink やMST 上の辺の処理をしているので2 ケースだけRuntime Error を引き起こしてしまっている... スタックを使って書き直すだけの気力がないのでまた今度直すとします.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
#define MAX_N (100000)
 
typedef long long lint;
 
struct Edge {
	int from, to, id;
	lint cost;
	bool inMST;
	Edge(int from, int to, lint cost, int id) : from(from), to(to), cost(cost), id(id){inMST = false;}
	Edge(){}
};
 
vector<Edge> G[MAX_N], v;
 
bool operator < (const Edge &a, const Edge &b)
{
	return (a.cost < b.cost);
}
 
bool operator > (const Edge &a, const Edge &b)
{
	return (b < a);
}
 
int par[MAX_N];
 
void init()
{
	for (int i = 0; i < MAX_N; i++)
		par[i] = i;
}
 
int find(int x)
{
	if (x == par[x]) return (x);
	return (par[x] = find(par[x]));
}
 
void unite(int u, int v)
{
	u = find(u); v = find(v);
	if (u == v) return;
	int x = u ^ v;
	x ^= ((rand() & 1) ? u : v);
	par[x] = x ^ u ^ v;
}
 
bool same(int u, int v)
{
	return (find(u) == find(v));
}
 
lint ans[MAX_N * 2];
int ord[MAX_N], dst[MAX_N], low[MAX_N];
bool vis[MAX_N];
lint cost;
 
void predfs(int u, int p, int &k)
{
	ord[u] = low[u] = k++;
	vis[u] = true;
	
	for (int i = 0; i < G[u].size(); i++){
		if (!vis[G[u][i].to] && v[G[u][i].id].inMST){
			predfs(G[u][i].to, u, k);
			low[u] = min(low[u], low[G[u][i].to]);
		}
		else if (G[u][i].to != p) low[u] = min(low[u], ord[G[u][i].to]);
	}
	dst[u] = k++;
}
 
typedef priority_queue<Edge, vector<Edge>, greater<Edge> > PQ;
 
PQ pool[MAX_N];
int id[MAX_N];
lint pCost[MAX_N];
 
PQ *dfs(int u, int p)
{
	PQ *pp = &pool[u];
	
	for (int i = 0; i < G[u].size(); i++){
		if (G[u][i].to != p && v[G[u][i].id].inMST){
			pCost[G[u][i].to] = G[u][i].cost; id[G[u][i].to] = G[u][i].id;
			PQ *qq = dfs(G[u][i].to, u);
			if (pp->size() < qq->size()) swap(pp, qq);
			while (qq->size()){
				pp->push(qq->top()); qq->pop();
			}
		}
		else if (G[u][i].to != p && !(ord[u] <= ord[G[u][i].to] && dst[G[u][i].to] <= dst[u])){
			pp->push(G[u][i]);
		}
	}
	
	while (pp->size() && ord[u] <= ord[pp->top().to] && dst[pp->top().to] <= dst[u])
		pp->pop();
	
	if (!pp->size()){
		if (~p) ans[id[u]] = -1;
	}
	else {
		if (~p) ans[id[u]] = cost - pCost[u] + pp->top().cost;
	}
	
	return (pp);
}
 
int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
		G[--a].push_back(Edge(-1, --b, w, i));
		G[b].push_back(Edge(-1, a, w, i));
		v.push_back(Edge(a, b, w, i));
	}
	
	sort(v.begin(), v.end());
	
	init();
	
	int eNum = 0;
	for (int i = 0; i < v.size(); i++){
		if (!same(v[i].from, v[i].to)){
			unite(v[i].from, v[i].to);
			cost += v[i].cost;
			eNum++;
			v[v[i].id].inMST= true;
		}
	}
	
	if (eNum != n - 1) for (int i = 0; i < m; i++) printf("-1\n");
	else {
		for (int i = 0; i < m; i++){
			if (!v[i].inMST) ans[i] = cost;
		}
		int k = 0;
		predfs(0, -1, k);
		dfs(0, -1);
		for (int i = 0; i < m; i++){
			printf("%lld\n", ans[i]);
		}
	}
	
	return (0);
}