na_o_ysのブログ

プログラミングなど

SRM 627 Div1 Med, GraphInversions

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13275

N 頂点, N 辺 (3 <= N <= 1000) の連結な無向グラフが与えられる. 各頂点は属性として値 v_i (1 <= v_i <= 1000) を持つ. 長さ K 以上の全ての単純路について, それぞれ v_i の系列で表した時に, 最も小さい転倒数 (inversion) を求めよ.

解法

それぞれの頂点に対して, 深さ K まで dfs する. 探索の計算量は N2 におさまる.
dfs しながら同時に, inversion を BIT で求める.
O(N2 log(N)).

実装

#define loop(n, i) for(int i=0;i<n;i++)

class GraphInversions
{
public:
    vector<int> G[1001];
    vector<int> V;
    int used[1001] = {};
    BIT *bit;

    int getMinimumInversions (vector <int> A, vector <int> B, vector <int> V, int K)
    {
        int N = A.size();
        this->V = V;
        loop (N, i) {
            G[A[i]].push_back(B[i]);
            G[B[i]].push_back(A[i]);
        }

        int ans = INF;
        loop (N, i) {
            bit = new BIT(1001);
            ans = min(ans, dfs(i, K));
            delete bit;
        }
        if (ans == INF) return -1;
        return ans;
    }

    int dfs(int i, int k) {
        if (used[i]) return INF;

        int crr = bit->sum(1000) - bit->sum(V[i]);
        if (k == 1) return crr;

        used[i] = 1;
        bit->add(V[i], 1);
        int rest = INF;
        for (int j : G[i]) if (!used[j]) {
            rest = min(rest, dfs(j, k-1));
        }
        used[i] = 0;
        bit->add(V[i], -1);

        if (rest == INF) return INF;
        return rest+crr;
    }
};