[C++]白俊23743号:密室脱出

10630 ワード
グラフィック理論 白駿 最小生成ツリー テキストリンク

質問リンク


23743号:密室脱出

問題の概要


私たちは部屋を脱出しなければなりませんが、ウォーフと非常口を設置することができます.ウォーフは各部屋を接続することができ、非常口は直接出口と部屋を接続することができます.すべての部屋の人が脱出できるように、緊急脱出口とウォーフを設置する最低費用を見つけなければならない.

方法


これはかんすい題と全く同じだと思います.入力のサイズは少し大きくなりますが、同じ方法で解くと、すべての入力が限られた時間で通過します.
出口を仮想の0番頂点と見なします.従って、出口と部屋との接続は、緊急出口を取り付けるコストの重み付け値である仮想的な幹線と見なすことができる.そして、0個の頂点を含むMSTを求める.MSTはクルースカアルゴリズムによって得られた.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

struct Edge {
	int v1, v2, w;
	bool operator<(const Edge& a) { return w < a.w; }
};

const int MAX = 301;
int parent[MAX];
vector<Edge> edges;

int Find(int a) {
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void) {
	int n;
	cin >> n;

	for (int i = 0; i <= n; i++) parent[i] = i;

	for (int i = 1; i <= n; i++) {
		int w;
		cin >> w;
		edges.push_back({ 0, i, w });
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w;
			cin >> w;
			
			if (i == j)
				continue;

			edges.push_back({ i, j, w });
		}
	}

	sort(edges.begin(), edges.end());

	int ans = 0;
	for (auto& i : edges) {
		if (Find(i.v1) != Find(i.v2)) {
			ans += i.w;
			Union(i.v1, i.v2);
		}
	}

	cout << ans << '\n';
	return 0;
}
jqueryのクリーンアップ
プログラマー全行程を完走しなかった選手