先週末のブルーブリッジカップの省模擬試験の最後の問題は最小生成木の問題でした。ちょうど MOOC でこの部分を見たばかりだったので、プリムアルゴリズムを学び、この問題を解決しました（おそらく）。競技後はこの種の問題をもっと考えようと思っています。問題リンク
最小生成木問題とは、無向グラフ G=(V,E) が与えられ、G 内のすべての点を接続し、辺の集合が E の部分集合である木を G の生成木（Spanning Tree）と呼び、重みが最小の生成木を最小生成木（Minimal Spanning Tree, MST）と呼びます。
一、クラスカルアルゴリズム#
クラスカルアルゴリズムは書きやすく、効率も非常に高いです。
紫書 p356 には次のように記述されています：
クラスカルアルゴリズムの第一歩は、すべての辺を重みの小さい順に並べることです。このステップはライブラリ関数 qsort または sort を直接使用できます。次に、重みの小さい順に各辺 (u, v) を考察します。
- 場合 1：u と v が同じ連結成分にある場合、(u, v) を追加すると環が形成されるため、選択できません。
- 場合 2：u と v が異なる連結成分にある場合、(u, v) を追加することは必ず最適です。 なぜでしょうか？以下に反証法を用います —— もしこの辺を追加しないで最適解 T を得られるなら、T+(u, v) には必ず 1 つの環があり、その環には少なくとも 1 つの辺 (u', v') の重みが (u, v) の重み以上である必要があります。その辺を削除すると、新しい木 T' = T + (u, v) - (u', v') は T よりも劣ることはありません。したがって、(u, v) を追加することは追加しないことよりも劣ることはありません。
以下は擬似コードです：
すべての辺（重みで）をソートし、i番目に小さい辺をe[i]（1 <= i < m）とする
MSTを空に初期化
連結成分を初期化し、各点を独立した連結成分として扱う
for(int i = 0; i < m; i++) {
if(e[i].u と e[i].v が同じ連結成分にない場合) {
辺e[i]をMSTに追加
e[i].uとe[i].vが属する連結成分を統合
}
}
上記の擬似コードで最も重要な部分は 「連結成分のクエリと統合」 です：任意の 2 点が同じ連結成分にあるかどうかを知る必要があり、これらの 2 つの連結成分を統合する必要があります。
この問題を処理するための簡潔で効率的なアルゴリズムがあります ——並列集合
ここでの指針は大佬の説明です：超素晴らしい並列集合～
各連結成分を 1 つの集合と見なす、この集合には連結成分内のすべての点が含まれます。これらの点は互いに接続されており、具体的な接続方法は重要ではありません。グラフ内では、各点はちょうど 1 つの連結成分に属します。集合表現に対応すると、各要素はちょうど 1 つの集合に属します。言い換えれば、グラフのすべての連結成分は、いくつかの互いに交差しない集合で表すことができます。
自分の並列集合のテンプレートを提供します。
#include <iostream>
using namespace std;
#define div 1000000007
typedef long long ll;
const int maxn = 1001;
int fa[maxn];//
inline void init(int n) {
for (int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int x) {//クエリ+パス圧縮：通過する各ノードの親ノードを根ノードに設定
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j) {
fa[find(i)] = find(j);//前者の親ノードを後者に設定
}
並列集合があれば、クラスカルアルゴリズムの完全なコードを簡単に提供できます。i 番目の辺の 2 つの端点の番号と重みがそれぞれ u [i]、v [i]、w [i] に保存され、ソート後の i 番目に小さい辺の番号が r [i] に保存されます（間接ソート、つまりソートのキーはオブジェクトの「コード」であり、オブジェクト自体ではありません）、p は並列集合です。
完全なコード：#
int cmp(const int i, const int j) { return w[i] < w[j]; } //間接ソート関数
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]);} //並列集合のfind
int Kruskal() {
int ans = 0;
for(int i = 0; i < n; i++) p[i] = i; //並列集合を初期化
for(int i = 0; i < m; i++) r[i] = i;
sort(r,r+m,cmp);
for(int i = 0; i < m; i++) {
int e = r[i];
int x = find(u[e]);//1つの端点が属する集合の番号を見つける
int y = find(v[e]);//もう1つの端点が属する集合の番号を見つける
if(x != y) { //異なる集合にいる場合、統合
ans += w[e];
p[x] = y;
}
}
return ans;
}
練習問題：#
問題番号 | 問題名（英語）| 備考 |
|--|--|--|--|
hdu1863| 通行工事 | 最小生成木 テンプレート問題
hdu1879| 続・通行工事 | 最小生成木 テンプレート問題
hdu1875| 通行工事再続 | 最小生成木 テンプレート問題
洛谷 P3366| 【テンプレート】最小生成木 | 最小生成木 テンプレート問題
1. hdu1863 通行工事#
問題の説明
省政府の「通行工事」の目標は、全省の任意の 2 つの村の間で道路交通を実現することです（ただし、直接の道路が接続されている必要はなく、間接的に道路で到達できればよい）。調査評価の結果、建設可能な道路のコストが記載された統計表が得られました。プログラムを作成して、全省の通行に必要な最低コストを計算してください。
入力
テスト入力は複数のテストケースを含みます。各テストケースの第 1 行には評価された道路の数 N、村の数 M（< 100）が与えられます；その後の N 行は村間の道路のコストに対応し、各行には 2 つの正整数が与えられ、2 つの村の番号とその間の道路のコスト（これも正整数）を示します。簡単のために、村は 1 から M まで番号が付けられます。N が 0 のとき、すべての入力が終了し、対応する結果は出力しません。
出力
各テストケースに対して、1 行で全省の通行に必要な最低コストを出力します。統計データが通行を保証するには不十分な場合は「？」と出力します。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
int N,M,cnt;
int u[maxn],v[maxn],w[maxn];
int r[maxn],fa[maxn];
bool cmp(const int r1, const int r2) {
return w[r1] < w[r2];
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int Kruskal() {
int ans = 0;
for(int i = 0; i < M; i++) fa[i] = i;//並列集合を初期化し、各点を独立した連結成分として扱う
for(int i = 0; i < N; i++) r[i] = i;//辺の番号を保存
sort(r, r+N, cmp);//辺を重みで小さい順にソート
for(int i = 0; i < N; i++) {
int e = r[i];
int x = find(u[e]);
int y = find(v[e]);
if(x != y) {
ans += w[e];
cnt++;
fa[x] = y;
}
}
return ans;
}
int main() {
while(cin >> N >> M) {
cnt = 0;
if(N == 0) break;
for(int i = 0; i < N; i++) {
cin >> u[i] >> v[i] >> w[i];
}
int ans = Kruskal();
if(cnt != M-1) cout << "?" << endl;
else cout << ans << endl;
}
return 0;
}
2.hdu1879 続・通行工事#
この問題は前の問題に比べて、すでに建設された道路のコストを 0 に設定するだけです。また、この問題の入力出力は cincout を使用できないようで、タイムアウトになることがあります。
問題の説明
省政府の「通行工事」の目標は、全省の任意の 2 つの村の間で道路交通を実現することです（ただし、直接の道路が接続されている必要はなく、間接的に道路で到達できればよい）。現在、町の道路統計表が得られ、任意の 2 つの町間の道路の建設コストとその道路がすでに開通している状態が記載されています。プログラムを作成して、全省の通行に必要な最低コストを計算してください。
入力
テスト入力は複数のテストケースを含みます。各テストケースの第 1 行には村の数 N（1 <N < 100）が与えられます；その後の N (N-1)/2 行は村間の道路のコストと建設状態に対応し、各行には 4 つの正整数が与えられ、2 つの村の番号（1 から N まで番号が付けられ）、その間の道路のコスト、および建設状態：1 は建設済み、0 は未建設を示します。
N が 0 のとき、入力が終了します。
出力
各テストケースの出力は 1 行で、全省の通行に必要な最低コストを出力します。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 5008;
int fa[101];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
struct Edge {
public:
int u, v, w;
bool operator<(const Edge &a)const{
return w < a.w;
}
}E[maxn];
int main() {
int N;
while(scanf("%d", &N) != EOF) {
int ans = 0;
if(N == 0) break;
int M = N*(N-1)/2;
for(int i = 1; i <= M; ++i) {
int flag;
scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].w, &flag);
if(flag) E[i].w = 0;
}
for(int i = 1; i <= N; ++i) fa[i] = i;//並列集合を初期化し、各点を独立した連結成分として扱う
sort(E+1,E+1+M);//辺を重みで小さい順にソート
for(int i = 1; i <= M; ++i) {
int x = find(E[i].u);
int y = find(E[i].v);
if(x != y) {
fa[x] = y;
ans += E[i].w;
}
}
printf("%d\n",ans);
}
return 0;
}
3.hdu1875 通行工事再続#
まずすべての頂点を入力し、その後各 2 つの頂点が適切な辺を構成できるかどうかを判断します。
問題の説明
皆さんは「百島湖」という場所を聞いたことがあるでしょう。百島湖の住民は異なる島々に住んでおり、他の島に行くときは小舟を使って移動します。政府は百島湖の発展を決定し、発展の最初の問題は交通問題です。政府は百島湖の全通行を実現することを決定しました！調査チーム RPRush が百島湖の状況を十分に理解した後、条件を満たす島々の間に橋を建設することを決定しました。条件とは、2 つの島間の距離が 10 メートル以上、1000 メートル以下であることです。もちろん、資金を節約するためには、任意の 2 つの島間に道路が通じていればよいのです。橋の価格は 100 元 / メートルです。
入力
入力には複数のデータセットが含まれます。入力は最初に整数 T（T <= 200）を含み、T はデータセットの数を示します。
各データセットは最初に整数 C（C <= 100）を含み、島の数を示し、その後 C 組の座標が続き、各島の座標を示します。これらの座標はすべて 0 <= x, y <= 1000 の整数です。
出力
各データセットの出力は 1 行で、橋を建設するための最小コストを示し、結果は小数点以下 1 桁を保持します。工事を実現できない場合は「oh!」と出力します。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 5008;
typedef long long ll;
struct Point {
int x,y;
} V[101];
struct Edge {
public:
int u, v;
double w;
bool operator<(const Edge &a)const{
return w < a.w;
}
}E[maxn];
int fa[105];
int find(int x) {
return fa[x] == -1 ? x : fa[x] = find(fa[x]);
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
int N;
scanf("%d", &N);
for(int i = 0; i < N; ++i) {
scanf("%d%d", &V[i].x, &V[i].y);
}
int k = 0;
for(int i = 0; i < N-1; ++i) {
for(int j = i+1; j < N; ++j) {
double d = sqrt( (V[i].x-V[j].x)*(V[i].x-V[j].x) +
(V[i].y-V[j].y)*(V[i].y-V[j].y) );
if (d <= 1000 && d >= 10) {
E[k].u = i;
E[k].v = j;
E[k].w = d*100;
k++;
}
}
}
for(int i = 0; i < N; ++i) fa[i] = -1;//並列集合を初期化し、各点を独立した連結成分として扱う
sort(E,E+k);//辺を重みで小さい順にソート
double ans = 0;
int cnt = 0;
for(int i = 0; i < k; ++i) {
int x = find(E[i].u);
int y = find(E[i].v);
if(x != y) {
fa[x] = y;
ans += E[i].w;
cnt++;
}
}
if (cnt == N-1) printf("%.1f\n",ans);
else printf("oh!\n");
}
return 0;
}
4.洛谷 P3366【テンプレート】最小生成木 #
テンプレート問題
#include <iostream>
#include <algorithm>
using namespace std;
const int maxm = 200000;
int fa[5005];//最大頂点数5000
int N,M,cnt;//頂点数 辺数
struct edge {
int u,v,w;
bool operator<(const edge& a) const {
return w < a.w;
}
} E[maxm];//最大辺数maxn
int find(int x) {
return fa[x] == -1 ? x : fa[x] = find(fa[x]);
}
int Kruskal() {
for(int i = 0; i < N; ++i) fa[i] = -1;
int ans = 0;
sort(E,E+M);
for(int i = 0; i < M; ++i) {
int x = find(E[i].u);
int y = find(E[i].v);
if(x != y) {
fa[x] = y;
ans += E[i].w;
cnt++;
}
}
if(cnt == N-1) return ans;
else return -1;
}
int main() {
scanf("%d%d", &N, &M);
for(int i = 0; i < M; ++i) {
scanf("%d%d%d", &E[i].u, &E[i].v,&E[i].w);
}
int ans = Kruskal();
if(ans == -1) printf("orz\n");
else printf("%d\n",ans);
return 0;
}
二、プリムアルゴリズム#
陳越おばあさんのデータ構造から
プリムアルゴリズムの基本的な考え方 —— 根ノードから始めて、小さな木を大きく育てる。ダイクストラアルゴリズムに似ています。
ダイクストラアルゴリズムの擬似コード：
void Dijkstra(Vertex s) {
while(1) {
V = 未収録の頂点の中でdistが最小のもの
if (そのようなVが存在しない)
break;
collected[V] = true;//Vを収録
for(Vの各隣接点W) {
if(collected[W] == false && dist[V] + E(V,W) < dist[W]) {
dist[W] = dist[V]+E<V,W>;
path[W] = V;
}
}
}
プリムアルゴリズムの擬似コード：
void Prim(Vertex s) {
while(1) {
V = 未収録の頂点の中でdistが最小のもの
if (そのようなVが存在しない)
break;
VをMSTに収録
for(Vの各隣接点W) {
if(Wが未収録 && E(V,W) < dist[W]) {
dist[W] = E<V,W>;
parent[W] = V;
}
}
}
プリムアルゴリズムの完全なコード#
double edge[maxn][maxn];//辺の重みを保存する~
int vis[maxn];//その点が訪問済みかどうか
double dist[maxn];
double ans;
double Prim() {
for(int i = 2; i <= n; i++) {
dist[i] = edge[1][i];//初期化：根ノード1からすべての点への距離を初期化
}
vis[1] = 1;////初期点1を収録 vis[i] == 0はまだ収録されていないことを示す
for(int i = 2; i <= n; i++) {
int min = INF;
int v = -1;
for(int j = 2; j <= n; j++) {//vを探す——未収録の頂点の中でdistが最小のもの
if(!vis[j] && dist[j] < min) {
min = dist[j];
v = j;
}
}
if(v != -1) {//vが見つかった~MSTに収録
vis[v] = 1;
ans += dist[v];
for(int j = 2;j <= n; j++) {//距離distを更新
if(!vis[j] && edge[v][j] < dist[j]) {//この点が未訪問で、木への距離よりも小さい場合は更新
dist[j] = edge[v][j];
}
}
}
}
return ans;
}