POJ 1378 - Power Cable Problem

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

概要

N 個のビルがあり，M 本のケーブルがビルを繋いでいる．

各ケーブルはループ状になっており，2個以上500個以下のビルを繋いでいる．

今，K 個のビルがダメージを受け，これらのビルに繋がっているケーブルはすべて使えなくなってしまった． このとき，1本も使えるケーブルに繋がっていないビルの数を答える． ただし，最初からどのケーブルにも繋がっていないようなビルも数に含めることとする．

制約

解法

どうやっても解ける気がする．

各ビルに，自分に繋がっているケーブルのインデックスのリストを持たせておき，ダメージを受けたビルに繋がっているケーブルのインデックスをすべて集めて sort + unique して，使えなくなったケーブルのリストを作る． そして，各ビルに対して自分に繋がっているケーブルのうち，さっき作ったリストに含まれていないようなものが1つでもあればスキップ，そうでなければカウント，というように実装した．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N, M, K;
 9   while (true) {
10     scanf("%d %d %d", &N, &M, &K);
11     vector<vector<int> > cables(N);
12     for (int i = 0; i < M; i++) {
13       int c;
14       scanf("%d", &c);
15       for (int j = 0; j < c; j++) {
16         int v;
17         scanf("%d", &v);
18         cables[v].push_back(i);
19       }
20     }
21 
22     vector<int> damaged;
23     for (int i = 0; i < K; i++) {
24       int v;
25       scanf("%d", &v);
26       for (vector<int>::const_iterator it = cables[v].begin(); it != cables[v].end(); ++it) {
27         damaged.push_back(*it);
28       }
29     }
30     sort(damaged.begin(), damaged.end());
31     damaged.erase(unique(damaged.begin(), damaged.end()), damaged.end());
32     int ans = N;
33     for (int i = 0; i < N; i++) {
34       for (vector<int>::const_iterator it = cables[i].begin(); it != cables[i].end(); ++it) {
35         vector<int>::const_iterator jt = lower_bound(damaged.begin(), damaged.end(), *it);
36         if (jt == damaged.end() || *jt != *it) {
37           --ans;
38           goto NEXT;
39         }
40       }
41 NEXT:
42       ;
43     }
44     printf("%d\n", ans);
45 
46     scanf("%d %d %d", &N, &M, &K);
47     if (N == -1) {
48       break;
49     }
50   }
51   return 0;
52 }
poj/1378.cc