AOJ 2511 Sinking islands

エディタいじってたら一日が終わっていました。

問題

Sinking islands | Aizu Online Judge

解法

まず, 最初から連結でない場合は橋を架ける必要がないので答えは 0 です。

他の場合は, どの時点で橋が連結でなくなるのかを調べます。
橋が連結でなくなったタイミング以降の島は最小全域木のようにして連結させることができます。

で, それより前の島も連結させなければなりませんが, これは
t, t-1, t-2, ... の島をだんだん連結させる感じで橋をつなげていくのが最適です(そうすれば余計に橋を架ける必要がないので)。

このようにして最小全域木の要領でコストの低い辺から連結させていけば良いです。

制約がかなり優しいのでオーダー的にいい加減に書いても通ります。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};



struct Edge
{	
	int u;
	int v;
	int cost;
	Edge() {}	
	Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}	
	bool operator<(const Edge& rhs) const {return cost < rhs.cost;}
};

const int MAXN = 222;
const int MAX = 1000100;
int N, M;
vector<int> vanish[MAX];
bool done[MAXN];
vector<Edge> G;

ll solve() {
	// 連結にならないなら答えは 1
	{
		UnionFind uf(N);
		for (Edge e : G)
			uf.unite(e.u, e.v);
		if (uf.count() > 1) return 0;
	}
	// どのタイミングで連結でなくなるかを考える
	// t=last で連結でなくなる場合, t=last+1 以降を連結にしてから
	// t=last, last-1, ... をちびちび連結させていけばよい
	int last = -1;
	memset(done, false, sizeof(done));
	for (int t = 0; t < MAX; t++) {
		if (vanish[t].empty()) continue;
		// こいつらは消える
		for (int v : vanish[t]) {
			done[v] = true;
		}
		// 残った頂点が連結かチェック
		UnionFind uf(N);
		for (Edge e : G) {
			if (done[e.u] || done[e.v]) continue;
			uf.unite(e.u, e.v);
		}
		int sz = 1;
		for (int i = 0; i < N; i++) 
			if (done[i]) sz++;
		if (uf.count() != sz) {
			last = t;
			break;
		}
	}
	UnionFind uf(N);
	ll ans = 0;
	memset(done, false, sizeof(done));
	for (int t = last; t < MAX; t++) {
		for (int v : vanish[t]) {
			done[v] = true;
		}
	}
	for (Edge e : G) {
		if (!done[e.u] || !done[e.v]) continue;
		if (uf.same(e.u, e.v)) continue;
		ans += e.cost;
		uf.unite(e.u, e.v);
	}
	for (int t = last-1; t >= 0; t--) {
		if (vanish[t].empty()) continue;
		for (int v : vanish[t]) 
			done[v] = true;
		for (Edge e : G) {
			if (!done[e.u] || !done[e.v]) continue;
			if (uf.same(e.u, e.v)) continue;
			ans += e.cost;
			uf.unite(e.u, e.v);
		}
	}
	return ans;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (cin >> N >> M) {
		if (N==0 && M==0) break;
		for (int i = 0; i < MAX; i++) 
			vanish[i].clear();
		for (int i = 0; i < N; i++) {
			int h;
			cin >> h;
			vanish[h].push_back(i);
		}
		G.clear();
		for (int i = 0; i < M; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			a--; b--;
			G.emplace_back(a, b, c);
		}
		sort(G.begin(), G.end());
		cout << solve() << endl;
	}
	return 0;
}