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; } };