ゆらのふなびと

競プロ, Python, C++

【グラフアルゴリズムとその例題】蟻本 2-5章 まとめ

蟻本 2-5章 のまとめです。各グラフアルゴリズムの概要と例題について。例題は一応ソースコードもつけておきます。

アルゴリズム

最短路問題

ベルマンフォード法

単一始点から他の各点への最短路を求める。負の長さの辺があってもOK。負閉路を持たない場合は高々 V-1回しかループが実行されないことを用いると、負閉路の検出にも適用できる。d[j] = min(d[j], d[i] + cost[i][j])という処理を繰り返し、更新されなくなったら終了。

計算量:  O(VE)

ダイクストラ

基本的にはベルマンフォード法と同じだが、負の長さの辺があるときには使えない。その代り計算量が下がる。ベルマンフォード法の式を、最短経路が小さい点から確定させながら適用する。

計算量:  O(E\log V) (プライオリティーキューを用いた場合)

ワーシャルフロイド法

上の2つとは異なり、全点最短路対を求める方法。簡単な3重ループで実現が可能だが、計算量は大きい。

計算量:  O(V^3)


3つのアルゴリズムの使い分けだが、基本的に以下のようになるだろう。

  • 制約が緩いとき、全点間の最短路を求めたいとき→ワーシャルフロイド
  • 制約がきついとき、始点が決まっているときダイクストラ
  • 負の長さの辺を含むとき→ベルマンフォード

なお、以上のアルゴリズムは基本的に「最短路長」を求めるものであるが、最短経路を更新するときに、前にいた点を持っておく配列を同時に更新することで最短経路の復元も可能である。


最小木問題

最小木問題とは、グラフ内のすべての頂点を含む木で重みの和が最小となるものを求める問題である。この問題は例えば、街の間に道路を建設するときに現れる。すべての街をつながなければならないが、各道路の建設コストが決まっており、そのコストの和を最小化したい、といった状況だ。この最小木問題を解くアルゴリズムが2つ存在する。

プリム法

プリム法ではまず始点 sを定め、集合 Xに加える。その後 X X\backslash Vをつなぐ辺のうち最小の重みの辺を最小木の辺集合 Tに追加し、 Tの端点のうち X\backslash V側にあるものを Xに追加する。これを繰り返してすべての頂点が Xに入ったとき、 T最小全域木となる。

計算量:  O(E\log V)

クラスカル

クラスカル法では、基本的に重みの小さい辺から順に Tに追加していく。ただしある辺 eを追加したとき Tに閉路ができてしまう場合はパスする。この判定は eの両端点が連結しているかどうかの判定であり、Union-Find木を用いて実装する。

プリム法との違いは以下の通り。

  1. プリム法がある始点から連続に木を伸ばしていくのに対し、クラスカル法では木を求める過程では分裂している可能性もある(遠くに1の辺が2つあったときなど)
  2. クラスカル法は非連結なグラフに適用した場合、「各連結成分内における最小全域木」の集合を求めることができる。


最小木問題の2つのアルゴリズムについて、使い分けがあるとすればクラスカル法の特徴の2に書いた点だろう。それ以外は計算量も同じなので正直好みの問題かもしれない。


例題

POJ 3255 Roadblocks

問題

3255 -- Roadblocks

めっちゃ端的に言うと、「2番目の最短路」を求める問題。始点と終点は決まっている。

解法

「1番目の最短路」ならダイクストラで簡単に出せる。では2番目の最短路は? 実はダイクストラ法を少し修正するだけでこれも求められる。

ポイントは以下の事柄である。

ある頂点 vへの2番目の最短路は、以下のいずれかである。

  1. uへの1番目の最短路 + (u -> v)
  2. uへの2番目の最短路 + (u -> v)

なぜ上の2つに限られるかといえば、もし「uへのi(>=3)番目の最短路 + (u -> v)」(★)がvへの2番目の最短路だったとすると、上の1., 2.はそれより短く、(★)が2番目の最短路であることに矛盾するからだ。(自分より短いものが2つ存在するのだから、(★)はvへの3番目以降の最短路である。)

よって、1番目の最短路と2番目の最短路のみを保存しながらダイクストラ法を進めることで、最終的な2番目の最短路を求めることができる。

#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;

struct edge {
    int to, cost;
    edge() {}
    edge(int t, int c) { to = t; cost = c; }
};

//first = minimum distance, second = num of a vertice
typedef pair<int, int> P;

const int INF = 100000000;
const int MAX_V = 5000;
const int MAX_E = 100000;

vector<edge> G[MAX_V];
int dist[MAX_V];
int dist2[MAX_V];
int V, E;

void input() {
    scanf("%d %d", &V, &E);
    REP(i, E) {
        int f, t, c;
        scanf("%d %d %d", &f, &t, &c);
        f--; t--;
        G[f].pb(edge(t, c));
        G[t].pb(edge(f, c));
    }
}

//s: start
void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P>> que;
    REP(i, V) dist[i] = INF,  dist2[i] = INF;
    dist[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second, d = p.first;
        if (dist2[v] < d) continue;
        REP(i, G[v].size()) {
            edge e = G[v][i];
            int d2 = d + e.cost;
            if (dist[e.to] > d2) {
                swap(dist[e.to], d2);
                que.push(P(dist[e.to], e.to));
            }
            if (dist2[e.to] > d2 && dist[e.to] < d2) {
                dist2[e.to] = d2;
                que.push(P(dist2[e.to], e.to));
            }
        }
    }
}

void solve() {
    dijkstra(0);
    printf("%d\n", dist2[V-1]);
}

int main() {
    input();
    solve();
    return 0;
}


POJ 3723 Conscription

問題

3723 -- Conscription

E人徴兵したい。1人徴兵するには通常10000ドルの費用がかかるが、何人かの間には1~9999の親密度 が設定されており、ある人を徴兵する際の費用は10000 - (すでに徴兵されている人の中で最も高い親密度)となる。このとき、全員を徴兵するために必要な費用の最小値を求めよ。

解法

人々を点、親密度を辺とみなすと、これは親密度を辺のコストとした"最大"全域木問題であることがわかる。より適切には、E人全員が辺でつながれているとは限らないので、求められているのは「各連結成分に対する"最大"全域木問題」を解くことである。これは"最小"であればクラスカル法をそのまま適用すればいいのであった。今回は最大と最小がひっくり返っているので、事前にコストの符号を逆転させて入れておくか、クラスカル法のキューのソート順を逆転させればよい。(下のコードは前者)

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

struct edge {
    int from, to, cost;
    edge() {}
    edge(int f, int t, int c) {
        from = f; to = t; cost = c;
    }
};

bool cmp (const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

int INF = 100000000;
const int MAX_V = 20010;
const int MAX_E = 50010;

int uni[MAX_V];
edge es[MAX_E];
int V, E;
int N, M;

void input() {
    scanf("%d%d%d", &N, &M, &E);
    V = N + M;
    REP(i, E) {
        int f, t, c;
        scanf("%d%d%d", &f, &t, &c);
        es[i] = edge(f, t + N, -c);
    }
}

void init_uf(int n) {
    REP(i, n) uni[i] = -1;
}

int root(int x) {
    if (uni[x] < 0) return x;
    else {
        return uni[x] = root(uni[x]);
    }
}

bool same(int x, int y) {
    return root(x) == root(y);
}

void unite(int x, int y) {
    x = root(x);
    y = root(y);

    if (x == y) return;

    if (uni[x] > uni[y]) swap(x, y);

    uni[x] += uni[y];
    uni[y] = x;
}

int kruskal() {
    sort(es, es + E, cmp);
    init_uf(V);
    int res = 0;
    REP(i, E) {
        edge e = es[i];
        if (!same(e.from, e.to)) {
            unite(e.from, e.to);
            res += e.cost;
        }
    }
    return res;
}

void solve() {
    printf("%d\n", 10000 * V + kruskal() );
}

int main() {
    int T;
    scanf("%d", &T);
    REP(i, T) {
        input();
        solve();
    }
    return 0;
}


POJ 3169 Layout

問題

3169 -- Layout

N頭の牛に1からNまでの番号がつけられており、これらを1列に並べる。ML組の牛は仲が良く、組(AL, BL, DL)に対し牛ALと牛BLの距離はDL以内でなければならない。また、MD組の牛は仲が悪く、組(AD, BD, DD)に対し牛AD,と牛BDの距離はDD以上でなければならない。ただし牛は同じ位置に複数存在することが可能である。これらの制約をすべて満たすような並び方のうち、1番の牛とN番の牛の距離の最大値を求めよ。もしそのような並び方が存在しない場合は-1を、いくらでも離れることができる場合は-2を出力せよ。

解法

「どこがグラフなんじゃい!」とつっこみたくなる問題。ところがこの問題は競プロ界に「牛ゲー」なる言葉を産み落とした実に誉れ高い問題なのである(?)

まず、問題を式に書き下してみよう。i番の牛の位置を d_iとすると、問題は以下のように定式化される。(ちょっと変な書き方してるけど以降のためです)

以下の条件のもとで d_{N} - d_{1}を最大化せよ。

  •  d_{i+1} + 0 \geq d_{i} \quad (i+1番の牛はiの番の牛より右側にいる)
  •  d_{AL} + DL \geq d_{BL}
  •  d_{BD} - DD \geq d_{AD}

はい。これ、線形計画問題シンプレックス法使って解けってか。ひゃーーー!!!!!!

とまあそんなはずはなく、実はこの問題、不等式を以下のように解釈するとグラフの最短路問題に帰着することができる。

 d_{i} + C \geq d_{j} \Leftrightarrow 点iから点jに向けて重みCの有効辺を張る (☆)

なんでこれでいいかっていうと、正直難しい。ダイクストラやベルマンフォードの式から明らかなように、 d_iを始点sから点iまでの最短距離とすると、 d_j + cost(j, i) \geq d_iが成り立つ。実は最短路問題とは、これらの制約のもとで d_t - d_sを最大化することである、らしい。

よくわからないのでとりあえず、牛ゲーの不等式を最短距離の不等式と同じ形にして、(☆)でグラフに変換したらいいと思う。意味はそのうちわかるでしょ。

で、グラフに変換できたらこのグラフは負の辺も含んでいるのでベルマンフォード使って最短路問題を解きます。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

struct edge {
    int from, to, cost;
    edge() {}
    edge(int f, int t, int c) {
        from = f; to = t; cost = c;
    }
};

const int INF = 100000000;
const int MAX_V = 10000;
const int MAX_E = 30000;

edge es[MAX_E];

int d[MAX_V];
int pre[MAX_V];
int V, E;
int N, ML, MD;

//for DAG
void input() {
    scanf("%d%d%d", &N, &ML, &MD);
    V = N;
    E = ML + MD + (V - 1);
    REP(i, ML) {
        int f, t, c;
        scanf("%d%d%d", &f, &t, &c);
        f--; t--;
        es[i] = edge(f, t, c);
    }
    REP(i, MD) {
        int f, t, c;
        scanf("%d%d%d", &f, &t, &c);
        f--; t--;
        es[i + ML] = edge(t, f, -c);
    }
    REP(i, V - 1) {
        es[i + ML + MD] = edge(i + 1, i, 0);
    }
}

//s: start
void bellman_ford(int s) {
    REP(i, V) d[i] = INF;
    d[s] = 0;
    REP(k, V) {
        bool update = false;
        REP(i, E) {
            edge e = es[i];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                pre[e.to] = e.from;
                update = true;
            }
        }
        if (!update) break;
    }

    int res = d[N-1];
    if (d[0] < 0) {
        res = -1;
    } else if (res == INF) {
        res = -2;
    }

    printf("%d\n", res);
}

void solve() {
    bellman_ford(0);
}

int main() {
    input();
    solve();
    return 0;
}


よーし次の章も読むぞー