AOJ 2251: Merry Christmas

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251

DAGの最小パス被覆問題。パスで点を覆う際の最小本数を求める。

まず二部グラフG(V,V';E)においてDAGでvからv'に辺がある時v∈V,v'∈V'に辺を張る。
すると答えは|V|-|最大マッチング|となる。有名問題らしい。

これを証明してみよう。
グラフを観察すると|V|=(パスの本数)+(パスで使われている辺の本数)なので、
(パスで使われている辺の本数)を最大化すればよい。

ここで上の二部グラフを考えると、
「DAG上でパスが存在する<=>二部グラフ辺を選んだ時、どの点も次数が高々1になる」
が成立しており、選んだ辺の集合は二部グラフのマッチングとなっている。
なので、最大マッチングを求めればパスの最小本数も求められたことになる。

あとこの問題に少し関連がありそうなものとしてdilworthの定理というものがある。

これはDAGにおいて
(どの二つの点間にパスが存在しない(安定集合の有向版)ような頂点の部分集合の最大サイズ) = (最小パス被覆の本数)
というものである。

二部グラフの|最大安定集合|=|最小辺カバー|みたいな感じ。

int main() {
    while(true) {
        cin >> N >> M >> L;
        if(N == 0 && M == 0 && L == 0) break;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(i != j) E[i][j] = INF;
            }
        }
        for(int i = 0; i < M; i++) {
            int from, to, cost;
            cin >> from >> to >> cost;
            E[from][to] = cost;
            E[to][from] = cost;
        }
        for(int i = 0; i < L; i++) cin >> R[i] >> T[i];
        for(int k = 0; k < N; k++) {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    E[i][j] = min(E[i][j], E[i][k] + E[k][j]);
                }
            }
        }
        for(int i = 0; i < L * 2; i++) G[i].clear();
        for(int i = 0; i < L; i++) {
            for(int j = 0; j < L; j++) {
                if(i == j) continue;
                if(T[j] - T[i] >= E[R[j]][R[i]]) {
                    add_edge(i, j + L);
                }
            }
        }
        cout << L - bipartite_matching() << endl;
    }
}

なぜか昔解いていた。(は？)
別解として航空スケジューリング問題に帰着するのもありそう。