POJ 1975 - Median Weight Bead

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

概要

N 個のビーズに関して「i 番目のビーズは j 番目のビーズよりも重い」という情報が M 個与えられる．

このとき，中央値になりえないビーズの数を答える．

制約

解法

ワーシャル・フロイドっぽく「i 番目のビーズよりも(重い|軽い)ビーズ」の数を求めて数えるだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int T;
 9   cin >> T;
10   while (T-- > 0) {
11     int N, M;
12     cin >> N >> M;
13     vector<vector<int> > lt(N, vector<int>(N, 0)), gt(N, vector<int>(N, 0));
14     for (int i = 0; i < M; i++) {
15       int u, v;
16       cin >> u >> v;
17       u--;  v--;
18       lt[u][v] = 1;
19       gt[v][u] = 1;
20     }
21 
22     for (int k = 0; k < N; k++) {
23       for (int i = 0; i < N; i++) {
24         for (int j = 0; j < N; j++) {
25           if (lt[i][k] && lt[k][j]) {
26             lt[i][j] = 1;
27           }
28         }
29       }
30     }
31     for (int k = 0; k < N; k++) {
32       for (int i = 0; i < N; i++) {
33         for (int j = 0; j < N; j++) {
34           if (gt[i][k] && gt[k][j]) {
35             gt[i][j] = 1;
36           }
37         }
38       }
39     }
40 
41     int ans = 0;
42     for (int i = 0; i < N; i++) {
43       if (count(lt[i].begin(), lt[i].end(), 1) > N/2
44           || count(gt[i].begin(), gt[i].end(), 1) > N/2) {
45         ++ans;
46       }
47     }
48     cout << ans << endl;
49   }
50   return 0;
51 }
poj/1975.cc