Tournamentの最小道被覆問題 (Minimum Path Cover Problem)

情報工学工房の問題で面白かったのでまとめます．
　POJ : 1776 -- Task Sequences

問題(意訳)

単純有向グラフ G=(V, A) が与えられる.ただし，Gの任意の2頂点 $u, v \in V (u \neq v)$ に対して， $(u, v) \in A$ または $(v, u) \in A$ を満たす(どちらも満たさない場合はない)．
Gの最小道被覆 (Minimum Path Cover) を求めよ．

入力は $|V| \times |V|$ の隣接行列で与えられる．成分(i, j)は0か1で，頂点iとjの間に弧があれば1，無ければ0である．

制約： $1 \le |V| \le 1,000$

方針

いくつか用語の説明をします．
[最小道被覆(Minimum Path Cover)]
G = (V, A) の道被覆(Path Cover)とは点素パスの集合PでVの各頂点がPに属するちょうど1つの道に属するという性質を満たすもの．
点素パスとは頂点の重複がない道．

[Tournament]
有向グラフがTournamentであるとは無向完全グラフのすべての辺に向き付けをおこなったもの．
Tournament (graph theory) - Wikipedia

一般グラフの最小道被覆問題はNP困難なのですがTournamentでは多項式時間アルゴリズムが存在します．また，この問題で与えられるグラフはTournamentの拡大グラフなので解くことができます．競技プログラミングではDAGの最小道被覆問題を解くアルゴリズムがよく知られていると思います．

この問題で与えられるグラフの両方向に弧が存在する頂点間に対して，どちらか片方のみに弧があると考えてtournamentとして考えます．tournamentに対して次の定理が成り立つのでそれを用いて問題を解きます．

[定理 (Redei 1934)]
Tournamentにはハミルトン路が存在する

証明：
頂点数に関する帰納法で証明を行う．
(基底段階 |V| = 1, 2)
グラフを全て列挙することによって正しさが確認できる．
(帰納段階)
$|V| = k$ で成り立つと仮定してk+1の場合を証明する．
任意の頂点数k+1のTournament G=(A,V)を考える．
任意に頂点 $v_{k+1}$ を取り除いたグラフ G'を考えるとG'は頂点数kなので帰納法の仮定からハミルトン路 $P'=(v_1, v_2, ..., v_k)$ が存在する．
Pに $v_{k+1}$ を加えてGのハミルトン路Pを構成する．
　1. $(v_{k+1}, v_1) \in A$ の場合
　　P'の先頭に $v_{k+1}$ を加えて $P = v_{k+1} P'$ とする．
　2. $(v_k, v_{k+1}) \in A$ の場合
　　P'の後ろに $v_{k+1}$ を加えて $P = P' v_{k+1}$ とする．
　3. それ以外
　　P'の先頭から添字の最も小さい頂点で $v_{k+1}$ からの弧が存在する頂点を $v_{cur}$ とする．
　　仮定から 2 < k かつ $(v_{k+1}, v_k) \in A$ であるからそのような頂点は存在する．
　　このとき， $v_{cur}$ の選び方から $(v_{cur-1}, v_{k+1}) \in A$ である（最小性論法）．
　　したがって， $P = v_1, ..., v_{cur-1}, v_{k+1}, v_{cur}, ..., v_k$ とする．　□

f:id:tatanaideyo:20161022144840p:plain:w1000
最小道被覆問題はパスの数の最小化でしたのでハミルトン路が存在すればそれが最適解となります．したがって，アルゴリズムとしては上の証明のように頂点を1つずつハミルトン路を保つように加えていきます．
計算時間は $O(|V|^2)$ です．より高速なアルゴリズムとして Bar-NoyとNor(1990)の $O(|V| \log|V|)$ のものが存在します(未読)．

ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    string s;

    while (cin >> n) {
        cin.ignore();

        // Input Graph
        vector<vector<bool> > g(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++i) {
            getline(cin, s);
            for (int j = 0; j < n; ++j) {
                if (s[j << 1] == '1')
                    g[i][j] = true;
            }
        }

        // Find a hamiltonian path in a like tournament g
        // n == 1
        if (n == 1) {
            cout << "1\n1\n1\n";
            continue;
        }

        // 2 <= n
        vector<int> next(n, -1);
        int head = 0, tail = 0;

        // add v in a path (head -> ... -> tail)
        for (int v = 1; v < n; ++v) {
            if (g[v][head]) { // v -> head -> ... -> tail
                next[v] = head;
                head = v;
            }
            else if (g[tail][v]) { // head -> ... -> tail -> v
                next[tail] = v;
                tail = v;
            }
            else { // head -> ... -> v_cur-1 -> v -> v_cur -> ... -> tail
                for (int cur = head; ; cur = next[cur]) {
                    if (g[cur][v] && g[v][next[cur]]) {
                        next[v] = next[cur];
                        next[cur] = v;
                        break;
                    }
                }
            }
        }

        // Output
        cout << "1\n" << n << '\n';
        for (int cur = head; cur != -1; cur = next[cur])
            cout << cur + 1 << (cur == tail ? '\n' : ' ');
    }

    return 0;
}