AtCoder で公開されている「典型アルゴリズム問題集」のF問題をC++で解いてみました。
F問題 最小全域木問題
問題はリンク先をご覧ください。
すべての頂点が連結となるように辺を設定します。その中で、辺の重みが最小となる辺の張り方を求めます。記事ではクラスカル法を紹介します。
解答案
辺を重みでソートして、重みが小さい順に辺を設定していきます。ただし、すでにその辺を設定していなくても連結している場合は、スキップします。このアルゴリズムは、クラスカル法と呼ばれています。
C++ プログラム例
クラスカル法を素直に実装します。UnionFind を使って連結しているかを調べています。最後に設定した辺の総和（result）を出力します。
以下が、C＋＋プログラムとなります。
#include <iostream>
#include <vector>
#include <queue>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
typedef long long int ll;
int main()
{
int n, m;
cin >> n >> m;
vector<int> u(m), v(m);
vector<ll> c(m);
vector<pair<ll, int>> weight(m);
for (int i = 0; i < m; ++i) {
cin >> u[i] >> v[i] >> c[i];
weight[i] = make_pair(c[i], i);
}
sort(weight.begin(), weight.end());
dsu uf(n);
ll result = 0;
for (int i = 0; i < m; ++i) {
ll cost = weight[i].first;
int index = weight[i].second;
if (!uf.same(u[index], v[index])) {
uf.merge(u[index], v[index]);
result += cost;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
最小全域木を求めるには、クラスカル法とプリム法があります。わたしには、クラスカル法の方が分かりやすく感じたため、この記事で紹介しました。
この問題集は、わたくしには、ちょうど良い難易度でした。すべての問題を紹介することができました。
