POJ 2239 - Selecting Courses

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

概要

n 種類の講義について，7日分の予定が与えられる． 1日に12コマ存在する． 同じ時間にやっている講義は同時には取れない． 同じ種類の講義は，7日間のどの時間にやっているものも全く同じものとする．

最大で何種類の講義をとることができるかを答える．

制約

• 1 <= n <= 300

解法

講義と時間で二部グラフを作って最大マッチングを求める．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 bool augument(const vector<vector<int> >& g, int u, vector<int>& match_to, vector<bool>& visited) // {{{
 6 {
 7   if (u < 0) {
 8     return true;
 9   }
10 
11   for (vector<int>::const_iterator it(g[u].begin()); it != g[u].end(); ++it) {
12     if (!visited[*it]) {
13       visited[*it] = true;
14       if (augument(g, match_to[*it], match_to, visited)) {
15         match_to[u] = *it;
16         match_to[*it] = u;
17         return true;
18       }
19     }
20   }
21   return false;
22 } // }}}
23 
24 int bipartite_matching(const vector<vector<int> >& g) // {{{
25 {
26   const int N = g.size();
27   vector<int> match_to(N, -1);
28   int match = 0;
29   for (int u = 0; u < N; u++) {
30     vector<bool> visited(N, false);
31     if (augument(g, u, match_to, visited)) {
32       match++;
33     }
34   }
35   return match;
36 } // }}}
37 
38 int main()
39 {
40   int N;
41   while (scanf("%d", &N) != EOF) {
42     vector<vector<int> > g(N + 7*12);
43     for (int i = 0; i < N; i++) {
44       int m;
45       scanf("%d", &m);
46       for (int j = 0; j < m; j++) {
47         int p, q;
48         scanf("%d %d", &p, &q);
49         --p;  --q;
50         g[i].push_back(N + 12*p+q);
51       }
52     }
53     printf("%d\n", bipartite_matching(g));
54   }
55   return 0;
56 }