POJ 2594 - Treasure Exploration

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

概要

ロボットを使って N 個の場所を調査したい． ロボットは任意の場所からスタートさせることができる．

M 本の道があり，ある場所から別の場所へ単方向に移動することができる． これを有向辺で表すとそのグラフは DAG になっている．

N 個すべての場所を調査するのに必要な最小のロボットの数を答える．

制約

解法

ようは DAG の最小パス被覆を求めればいい．

最初にワーシャル・フロイドで「場所 i から場所 j へ到達できる」ような i, j を計算して，そのすべてに有向辺を張っておき，二部マッチングすればいい．

ワーシャル・フロイドをして辺を張っておかないと，以下のようなケースで 3 と答えて死ぬことになる． 

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 static const int K = 1000;
 5 
 6 bool bm_augment(const bool g[K][K], int N, int u, int *match_to, bool *visited) // {{{
 7 {
 8   if (u < 0) {
 9     return true;
10   }
11 
12   for (int v = 0; v < N; v++) {
13     if (g[u][v] && !visited[v]) {
14       visited[v] = true;
15       if (bm_augment(g, N, match_to[v], match_to, visited)) {
16         match_to[u] = v;
17         match_to[v] = u;
18         return true;
19       }
20     }
21   }
22   return false;
23 } // }}}
24 
25 int bipartite_matching(const bool g[K][K], int N)  // {{{
26 {
27   static int match_to[K];
28   fill_n(match_to, N, -1);
29   int match = 0;
30   for (int u = 0; u < N; u++) {
31     static bool visited[K];
32     fill_n(visited, N, false);
33     if (bm_augment(g, N, u, match_to, visited)) {
34       match++;
35     }
36   }
37   return match;
38 } // }}}
39 
40 int main()
41 {
42   int N, M;
43   while (scanf("%d %d", &N, &M) != EOF && N != 0) {
44     static bool dist[500][500];
45     for (int i = 0; i < N; i++) {
46       fill_n(dist[i], N, false);
47     }
48     for (int i = 0; i < M; i++) {
49       int u, v;
50       scanf("%d %d", &u, &v);
51       --u;  --v;
52       dist[u][v] = true;
53     }
54 
55     for (int k = 0; k < N; k++) {
56       for (int i = 0; i < N; i++) {
57         for (int j = 0; j < N; j++) {
58           if (dist[i][k] && dist[k][j]) {
59             dist[i][j] = true;
60           }
61         }
62       }
63     }
64 
65     static bool g[K][K];
66     for (int i = 0; i < 2*N; i++) {
67       fill_n(g[i], 2*N, false);
68     }
69     for (int i = 0; i < N; i++) {
70       for (int j = 0; j < N; j++) {
71         if (dist[i][j]) {
72           g[i][j+N] = true;
73         }
74       }
75     }
76     const int r = bipartite_matching(g, 2*N);
77     printf("%d\n", N-r);
78   }
79   return 0;
80 }
poj/2594.cc