AOJ 2432 Sports Days 2.0

問題文

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

解法

行列累乗で解く。
A[u][v] := u -> v のウォークで最大となるもの
と定義すると、A を n 回かけた行列 An は、長さ n のウォークについて考えたものになる。これは超典型。
行列積の計算だが、A[i][j] = max(A[i][j], B[i][k] + C[k][j]) とする。
max は結合則を満たすので、上で定義した行列積について繰り返し二乗法を用いることができる。

よって、入力で行列を作ったあと、ウォークの長さ n についての二分探索をする。これで長さは求まる。
このとき、パスを陽に持つと当然TLEするので、パスの復元は後にやる必要がある。
具体的に出力する必要があるパスの長さは最大100だから、これは愚直に dp で求め直してやれば良い。

計算量は O(V^3) だが、まあまあ重いため、定数倍に注意。
以下の実装は定数倍改善をあまり考慮せずに書いているが、TL 3sec のところ 2.6sec だった。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using matrix = vector<vector<int>>;

matrix mat_op(matrix a, matrix b) {
    const int n = a.size();
    matrix res(n, vector<int>(n, -1));
    for(int k = 0; k < n; ++k) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(a[i][k] == -1 || b[k][j] == -1) continue;
                res[i][j] = max(res[i][j], a[i][k] + b[k][j]);
            }
        }
    }
    return res;
}

matrix matpow(matrix a, int n) {
    const int V = a.size();
    matrix res(V, vector<int>(V, -1));
    for(int i = 0; i < V; ++i) {
        res[i][i] = 0;
    }
    while(n > 0) {
        if(n & 1) res = mat_op(move(res), a);
        a = mat_op(a, a);
        n >>= 1;
    }
    return res;
}


int main() {
    int V, E, K; cin >> V >> E >> K;
    matrix a(V, vector<int>(V, -1));
    for(int i = 0; i < V; ++i) {
        a[i][i] = 0;
    }
    for(int i = 0; i < E; ++i) {
        int u, v, c; cin >> u >> v >> c;
        a[u][v] = max(a[u][v], c);
    }

    auto check = [&] (int cnt) {
        const auto res = matpow(a, cnt);
        for(int i = 0; i < V; ++i) {
            for(int j = 0; j < V; ++j) {
                if(res[i][j] >= K) return true;
            }
        }
        return false;
    };
    int lb = 0, ub = K + 1;
    while(ub - lb > 1) {
        const auto mid = (lb + ub) >> 1;
        (check(mid) ? ub : lb) = mid;
    }

    if(ub == K + 1) {
        cout << -1 << endl;
        return 0;
    }

    cout << ub << endl;
    if(ub <= 100) {
        vector<int> dp(V);
        vector<vector<int>> path(V);
        for(int i = 0; i < V; ++i) {
            path[i] = {i};
        }
        for(int i = 0; i < ub; ++i) {
            vector<int> ndp(V, -1), nfrom(V, -1);
            vector<vector<int>> npath(V);
            for(int from = 0; from < V; ++from) {
                if(dp[from] == -1) continue;
                for(int to = 0; to < V; ++to) {
                    if(from == to || a[from][to] == -1) continue;
                    if(ndp[to] < dp[from] + a[from][to]) {
                        ndp[to] = dp[from] + a[from][to];
                        nfrom[to] = from;
                    }
                }
            }
            for(int j = 0; j < V; ++j) {
                if(nfrom[j] == -1) continue;
                npath[j] = path[nfrom[j]];
                npath[j].push_back(j);
            }
            dp = move(ndp);
            path = move(npath);
        }
        vector<int> ans_path;
        int maxi = -1;
        for(int i = 0; i < V; ++i) {
            if(dp[i] > maxi) {
                maxi = dp[i];
                ans_path = path[i];
            }
        }
        for(int i = 0; i <= ub; ++i) {
            cout << ans_path[i] << " \n"[i == ub];
        }
    }
}

感想

典型良問と言えるのかな。
AOJ-ICPC 700点 にしては簡単だった。