最小全域木：クラスカル法（4題）

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本の章末で紹介されている問題をひたすら解いている。
今回はグラフの最小全域木を求める問題。
最小全域木とは、（連結なグラフに対して）任意の2つの頂点についてそれをつなぐ経路が存在するような部分木のうち、辺の合計コストが最小のもののこと。要するに辺が"全域"に渡る最小コストの部分木。
今回の問題はすべてクラスカル法で解いた。ほかにもプリム法があるけど、クラスカル法がユニオンファインド木を使うのでかっこいいなあと思って使った次第。一度関数を作ればあとは使い回せるので、全体的に楽だった。しかもユニオンファインドは蟻本の実装そのままだし。

POJ1258: Agri-Net

1258 -- Agri-Net

問題概要

1258 Agri-Net - PKU Wiki*
最小全域木を作る問題。

解法

クラスカル法。実装は蟻本P.101の通りにやった。

#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX_E = 100 * 99 / 2; // 100C2
struct edge{ int u, v, cost; };
edge es[MAX_E];
int V, E; // 頂点数と辺数

//--------Union-Find木------------
vector<int> par; // 親
vector<int> rnk; // 深さ

// Union-Find木の初期化
void init_union_find(int n) {
  par  = vector<int>(n);
  rnk = vector<int>(n);
  for (int i = 0; i < n; i++) {
    par[i] = i;
    rnk[i] = 0;
  }
}

// 木の根を求める
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rnk[x] < rnk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
  }
}

// xとyが同じ集合に属するか否か
bool same(int x, int y) {
  return find(x) == find(y);
}

//----------クラスカル法------------
bool comp(const edge& e1, const edge& e2) {
  return e1.cost < e2.cost;
}
int kruskal() {
  sort(es, es + E, comp); // edge.costの小さい順
  init_union_find(V); // Union-Findの初期化
  int res = 0;
  for (int i = 0; i < E; i++) {
    edge e = es[i];
    if (!same(e.u, e.v)) {
      unite(e.u, e.v);
      res += e.cost;
    }
  }
  return res;
}

int main() {
  // 初期化
  while ( cin >> V ) {
    E = V * (V-1) /2;
    int c;
    int k = 0;
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        if (j >= i) {
          cin >> c;
        } else {
          cin >> c;
          edge e = {i, j, c};
          es[k++] = e;
        }
      }
    }
    // 最小全域木をクラスカル法で求める
    int res = kruskal();
    // 出力
    cout << res << endl;
  }
}

POJ2377: Bad Cowtractors

問題概要

2377 -- Bad Cowtractors
最小全域木、ではなく、「最大」全域木を作る問題。
つまり、コストの和が最大になるような全域木を作る。

解法

クラスカル法。辺のソートをコストの大きい順にするだけ。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX_E = 20000;
struct edge{ int u, v, cost; };
edge es[MAX_E];
int V, E; // 頂点数と辺数

//--------Union-Find木------------
vector<int> par; // 親
vector<int> rnk; // 深さ

// Union-Find木の初期化
void init_union_find(int n) {
  par  = vector<int>(n);
  rnk = vector<int>(n);
  for (int i = 0; i < n; i++) {
    par[i] = i;
    rnk[i] = 0;
  }
}

// 木の根を求める
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rnk[x] < rnk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
  }
}

// xとyが同じ集合に属するか否か
bool same(int x, int y) {
  return find(x) == find(y);
}

//----------クラスカル法------------
bool comp(const edge& e1, const edge& e2) {
  return e1.cost > e2.cost; // 大きい順
}
int kruskal() {
  sort(es, es + E, comp); // edge.costの大きい順
  init_union_find(V); // Union-Findの初期化
  int res = 0;
  int cnt_e = 0; // 加える辺を数える
  for (int i = 0; i < E; i++) {
    edge e = es[i];
    if (!same(e.u, e.v)) {
      unite(e.u, e.v);
      res += e.cost;
      cnt_e++;
    }
  }
  if (cnt_e == V - 1) {
    return res;
  } else {
    return -1; // 全域木を作れなければ-1
  }
}
int main() {
  // 初期化
  cin >> V >> E;
  int a, b, c;
  for (int i = 0; i < E; i++) {
    cin >> a >> b >> c;
    a--; b--;
    edge e = {a, b, c};
    es[i] = e;
  }
  // クラスカル法で最大全域木を計算
  int max_cost = kruskal();
  // 出力
  cout << max_cost << endl;
}

AOJ2224: Save your cat

問題概要

Save your cat | Aizu Online Judge
N個の頂点とM個の辺を持った無向グラフがある。グラフの閉路がすべてなくなるように辺を取り除きたい。辺のコストは辺の長さである。取り除く辺のコストの最小値を求めよ。
2 <= N <= 10000
1 <= M

解法

辺を取り除くと考えるのではなく、残す辺で全域木を作ると考えれば、これも最大全域木問題になる。クラスカル法で解く。

#include <typeinfo>
#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
struct edge{ int u, v; double cost; };
vector<edge> es;
int V, E; // 頂点数と辺数

//--------Union-Find木------------
vector<int> par; // 親
vector<int> rnk; // 深さ

// Union-Find木の初期化
void init_union_find(int n) {
  par  = vector<int>(n);
  rnk = vector<int>(n);
  for (int i = 0; i < n; i++) {
    par[i] = i;
    rnk[i] = 0;
  }
}

// 木の根を求める
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rnk[x] < rnk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
  }
}

// xとyが同じ集合に属するか否か
bool same(int x, int y) {
  return find(x) == find(y);
}

//----------クラスカル法------------
bool comp(const edge& e1, const edge& e2) {
  return e1.cost > e2.cost; // 大きい順
}
double kruskal() {
  sort(es.begin(), es.end(), comp); // edge.costの大きい順
  init_union_find(V); // Union-Findの初期化
  double res = 0;
  for (int i = 0; i < E; i++) {
    edge e = es[i];
    if (!same(e.u, e.v)) {
      unite(e.u, e.v);
      res += e.cost;
    }
  }
  return res;
}

int main() {
  // 初期化
  cin >> V >> E;
  vector<int> vx = vector<int>(V);
  vector<int> vy = vector<int>(V);
  es = vector<edge>(E);
  for (int i = 0; i < V; i++) {
    cin >> vx[i] >> vy[i];
  }
  double l;
  int p, q;
  double total_cost = 0;
  for (int i = 0; i < E; i++) {
    cin >> p >> q;
    p--; q--;
    l = sqrt(static_cast<double>((vx[p] - vx[q])*(vx[p] - vx[q]) + (vy[p] - vy[q])*(vy[p] - vy[q])));
    edge e = {p, q, l};
    es[i] = e;
    total_cost += l;
  }
  // クラスカル法で最大全域木のコストを計算
  double kr = kruskal();
  // 出力
  printf("%.4f\n", total_cost - kr);
}

POJ2395: Out of Hay

2395 -- Out of Hay

問題概要

最小全域木の中にある最大コストの辺を求める。

解法

単純なクラスカル法。

#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX_M = 10000;
struct edge{ int u, v, cost; };
edge es[MAX_M];
int V, E; // 頂点数と辺数

//--------Union-Find木------------
vector<int> par; // 親
vector<int> rnk; // 深さ

// Union-Find木の初期化
void init_union_find(int n) {
  par  = vector<int>(n);
  rnk = vector<int>(n);
  for (int i = 0; i < n; i++) {
    par[i] = i;
    rnk[i] = 0;
  }
}

// 木の根を求める
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rnk[x] < rnk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
  }
}

// xとyが同じ集合に属するか否か
bool same(int x, int y) {
  return find(x) == find(y);
}

//----------クラスカル法------------
bool comp(const edge& e1, const edge& e2) {
  return e1.cost < e2.cost;
}
int kruskal() {
  sort(es, es + E, comp); // edge.costの小さい順
  init_union_find(V); // Union-Findの初期化
  // res は最大辺の長さ
  int res = 0;
  for (int i = 0; i < E; i++) {
    edge e = es[i];
    if (!same(e.u, e.v)) {
      unite(e.u, e.v);
      res = max(res, e.cost);
    }
  }
  return res;
}

int main() {
  // 初期化
  cin >> V >> E;
  int a, b, l;
  for (int i = 0; i < E; i++) {
    cin >> a >> b >> l;
    a--; b--;
    edge e = {a, b, l};
    es[i] = e;
  }
  // 最小全域木をクラスカル法で求める
  int res = kruskal();
  // 出力
  cout << res << endl;
}