AOJ 0575 - Festivals in JOI Kingdom

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

解法

まず各ノード \(v\) について、お祭りが開催されているノードまでの最短距離 \(\mbox{dist}(v)\) を求める。 これはお祭りが開催されているノードからダイクストラをすればよい。 最短距離を求めてしまえば、エッジの長さの情報は以降不要となる。

次に、各エッジ \((u, v)\) の重み \(w\) を \(\mbox{min}(\mbox{dist}(u), \mbox{dist}(v))\) と設定する。 これは、このエッジを使うと最大でもお祭りが開催されているノードまでの距離が \(w\) のノードを通ることになることを表している。 このグラフの上で、重みを負とみて最小全域木を求める。 最適なパスはこの最小全域木に含まれるエッジのみを通って達成できる。

クラスカル法で最小全域木を作るとき、Union-Find で併合した過程を表す二分木を作る。 このときに新たに追加されるノードは \(N-1\) 個である。 新たに追加するノードの \(\mbox{dist}\) は、併合したときのエッジの重みとする。

このようにして得られた二分木を用いると、\(S, T\) 間の最適なパスの距離は二分木上の葉ノードにある \(S, T\) の LCA (Lowest Common Ancestor) の \(\mbox{dist}\) となる。 LCA は平方分割を用いて \(O(N)\) で構築、\(O(\sqrt[]{N})\) でクエリに答えることができる。 TopCoder の Algorithm Tutorials を参考にした。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <queue>
  4 #include <algorithm>
  5 using namespace std;
  6 static const int INF = 1000000000;
  7 static const int MAXN = 100000;
  8 static const int MAXM = 200000;
  9 static const int SECTION_SIZE = 450;
 10 
 11 struct DisjointSet/*{{{*/
 12 {
 13   vector<int> parent;
 14 
 15   int root(int x)
 16   {
 17     if (parent[x] < 0) {
 18       return x;
 19     } else {
 20       parent[x] = root(parent[x]);
 21       return parent[x];
 22     }
 23   }
 24 
 25   explicit DisjointSet(int n) : parent(n, -1) {}
 26 
 27   bool unite(int x, int y)
 28   {
 29     const int a = root(x);
 30     const int b = root(y);
 31     if (a != b) {
 32       if (parent[a] < parent[b]) {
 33         parent[a] += parent[b];
 34         parent[b] = a;
 35       } else {
 36         parent[b] += parent[a];
 37         parent[a] = b;
 38       }
 39       return true;
 40     } else {
 41       return false;
 42     }
 43   }
 44 
 45   bool find(int x, int y) { return root(x) == root(y); }
 46   int size(int x) { return -parent[root(x)]; }
 47 };/*}}}*/
 48 
 49 struct edge
 50 {
 51   int u, v, c;
 52   bool operator<(const edge& e) const { return c > e.c; }
 53 };
 54 
 55 void lca_dfs(const vector<int> *tree, const int *parent, int *P, int *L, int depth, int n)
 56 {
 57   L[n] = depth;
 58   if (depth < SECTION_SIZE) {
 59     P[n] = 1;
 60   } else {
 61     if (!(depth % SECTION_SIZE)) {
 62       P[n] = parent[n];
 63     } else {
 64       P[n] = P[parent[n]];
 65     }
 66   }
 67   for (vector<int>::const_iterator it = tree[n].begin(); it != tree[n].end(); ++it) {
 68     lca_dfs(tree, parent, P, L, depth+1, *it);
 69   }
 70 }
 71 
 72 int lca_query(const int *parent, const int *P, const int *L, int u, int v)
 73 {
 74   while (P[u] != P[v]) {
 75     if (L[u] > L[v]) {
 76       u = P[u];
 77     } else {
 78       v = P[v];
 79     }
 80   }
 81   while (u != v) {
 82     if (L[u] > L[v]) {
 83       u = parent[u];
 84     } else {
 85       v = parent[v];
 86     }
 87   }
 88   return u;
 89 }
 90 
 91 int main()
 92 {
 93   int N, M, K, Q;
 94   scanf("%d %d %d %d", &N, &M, &K, &Q);
 95   vector<vector<pair<int,int> > > g(N);
 96   static edge edges[MAXM];
 97   for (int i = 0; i < M; i++) {
 98     edge& e = edges[i];
 99     scanf("%d %d %d", &e.u, &e.v, &e.c);
100     --e.u;  --e.v;
101     g[e.u].push_back(make_pair(e.v, e.c));
102     g[e.v].push_back(make_pair(e.u, e.c));
103   }
104 
105   static int dist[2*MAXN];
106   fill_n(dist, N, INF);
107   priority_queue<pair<int,int> > q;
108   for (int i = 0; i < K; i++) {
109     int F;
110     scanf("%d", &F);
111     --F;
112     dist[F] = 0;
113     q.push(make_pair(0, F));
114   }
115 
116   while (!q.empty()) {
117     const int c = -q.top().first;
118     const int n = q.top().second;
119     q.pop();
120     if (dist[n] < c) {
121       continue;
122     }
123     for (vector<pair<int,int> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
124       const int m = it->first;
125       const int cc = c + it->second;
126       if (cc < dist[m]) {
127         dist[m] = cc;
128         q.push(make_pair(-cc, m));
129       }
130     }
131   }
132 
133   for (int i = 0; i < M; i++) {
134     edge& e = edges[i];
135     e.c = min(dist[e.u], dist[e.v]);
136   }
137   sort(edges, edges+M);
138   DisjointSet s(N);
139   static int m[MAXN];
140   for (int i = 0; i < N; i++) {
141     m[i] = i;
142   }
143   static int parent[2*MAXN];
144   static vector<int> tree[2*MAXN];
145   int uniq = N;
146   for (int i = 0; i < M; i++) {
147     const edge& e = edges[i];
148     const int x = s.root(e.u);
149     const int y = s.root(e.v);
150     if (s.unite(x, y)) {
151       parent[m[x]] = parent[m[y]] = uniq;
152       dist[uniq] = min(dist[m[x]], dist[m[y]]);
153       tree[uniq].push_back(m[x]);
154       tree[uniq].push_back(m[y]);
155       m[s.root(x)] = uniq;
156       ++uniq;
157     }
158   }
159 
160   static int P[2*MAXN], L[2*MAXN];
161   lca_dfs(tree, parent, P, L, 0, uniq-1);
162 
163   for (int i = 0; i < Q; i++) {
164     int S, T;
165     scanf("%d %d", &S, &T);
166     --S;  --T;
167     const int u = lca_query(parent, P, L, S, T);
168     printf("%d\n", dist[u]);
169   }
170 
171   return 0;
172 }