AOJ 2251 - Merry Christmas

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

概要

N 個の家を M 本の道が双方向に距離 d[i] で繋いでいる．

L 個の「家 p[i] に時刻 t[i] にプレゼントを届けよ」というリクエストをすべて満たすのに必要な最小のサンタの数を答える．

サンタは時刻 0 にいずれかの家からスタートし，単位時間あたりに単位距離進むことができる． 一人のサンタが何個のリクエストを処理してもかまわない．

制約

解法

JAG の講評も参考に． 2010/Practice/模擬地区予選/講評 - ACM-ICPC Japanese Alumni Group

i 番目のリクエストを処理した後に j 番目のリクエストを処理できるかどうかは

dist[p[i]][p[j]] <= t[j] - t[i]

で判定できる．ここで dist[u][v] は u, v 間の最短距離で，ワーシャル・フロイドで先に計算しておく．

「i 番目のリクエストを処理した後に j 番目のリクエストを処理できる」という関係を有向辺で繋ぐとこれは DAG になり，この最小パス被覆を求める問題に帰着できる．

DAG の最小パス被覆は二部マッチングによって解くことができる．

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