POJ 2832 - How Many Pairs?

http://poj.org/problem?id=2832

概要

頂点数 N，エッジ数 M の無向グラフ G が与えられる．すべてのエッジには長さがある． Q 個の「min_pair(u, v) <= A を見たす u, v の組み合わせの数はいくつか」というクエリに答える．

  1. G に含まれる任意の空でないパス p に対して，max_len(p) を「p に含まれるエッジの長さの最大値」と定義する
  2. Gの頂点 u, v に対して，min_pair(u, v) をmin { max_len(p) | p は u, v を繋ぐパス } と定義する

制約

解法

クラスカル法のイメージで，長さが小さいエッジから Union-Find でノードを併合しながら予め答えを求めておく． サイズが n の集合とサイズが m の集合を併合するときに組み合わせの数は n * m 個増えることを利用し， 「長さが c 以下のエッジのみを使った場合の組み合わせの数」を足し合わせながら計算していけばよい． エッジのソートが必要なので，ここまでで O(M log M)．

あとはクエリがきたときに c に関して二分探索で upper_bound をとってくれば O(Q log M) でクエリに答えることができる．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 static const int MAXN = 10000, MAXM = 50000;
 5 
 6 struct DisjointSet/*{{{*/
 7 {
 8   int parent[MAXN];
 9 
10   int root(int x)
11   {
12     if (parent[x] < 0) {
13       return x;
14     } else {
15       parent[x] = root(parent[x]);
16       return parent[x];
17     }
18   }
19 
20   explicit DisjointSet(int n)
21   {
22     fill_n(parent, n, -1);
23   }
24 
25   bool unite(int x, int y)
26   {
27     const int a = root(x);
28     const int b = root(y);
29     if (a != b) {
30       if (parent[a] < parent[b]) {
31         parent[a] += parent[b];
32         parent[b] = a;
33       } else {
34         parent[b] += parent[a];
35         parent[a] = b;
36       }
37       return true;
38     } else {
39       return false;
40     }
41   }
42 
43   bool find(int x, int y) { return root(x) == root(y); }
44   int size(int x) { return -parent[root(x)]; }
45 };/*}}}*/
46 
47 struct edge
48 {
49   int u, v, c;
50   bool operator<(const edge& e) const { return c < e.c; }
51 };
52 
53 int main()
54 {
55   int N, M, Q;
56   scanf("%d %d %d", &N, &M, &Q);
57   static edge es[MAXM];
58   for (int i = 0; i < M; i++) {
59     scanf("%d %d %d", &es[i].u, &es[i].v, &es[i].c);
60     --es[i].u; --es[i].v;
61   }
62   sort(es, es+M);
63 
64   static DisjointSet s(N);
65   static int cs[MAXM+2], as[MAXM+2];
66   int acc = 0;
67   for (int i = 0; i < M; i++) {
68     const int c = es[i].c;
69     const int u = s.root(es[i].u);
70     const int v = s.root(es[i].v);
71     if (u != v) {
72       acc += s.size(u) * s.size(v);
73       s.unite(u, v);
74     }
75     cs[i+1] = c;
76     as[i+1] = acc;
77   }
78   static const int INF = 100000000;
79   cs[M+1] = INF;
80   as[M+1] = acc;
81 
82   while (Q-- > 0) {
83     int A;
84     scanf("%d", &A);
85     const int idx = upper_bound(cs, cs+M+2, A) - cs - 1;
86     printf("%d\n", as[idx]);
87   }
88   return 0;
89 }
poj/2832.cc