POJ 3342 - Party at Hali-Bula

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

概要

n 人の従業員からできるだけ多くの人をパーティに招待したい．

しかし，ある従業員とその上司を同時にパーティに招待しないようにしなければならない． この組織においては，Big Boss を除いてどの従業員も上司は一人しかいない．

このとき，パーティに招待できる最大の人数と，招待の仕方が唯一通りしかないかどうかを答える．

制約

解法

木構造に従って，葉のほうから

を埋めていく DP．

唯一通りかどうかの判定がやや面倒．唯一通りじゃなくなるのは大きく分けて，

の2つ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 using namespace std;
 5 
 6 void dfs(const vector<vector<int> >& g, int n, vector<vector<int> >& dp, vector<vector<bool> >& uniq)
 7 {
 8   dp[n][0] = 0; dp[n][1] = 1;
 9   uniq[n][0] = uniq[n][1] = true;
10   for (vector<int>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
11     dfs(g, *it, dp, uniq);
12     if (dp[*it][0] == dp[*it][1]) {
13       dp[n][0] += dp[*it][0];
14       uniq[n][0] = false;
15     } else if (dp[*it][0] < dp[*it][1]) {
16       dp[n][0] += dp[*it][1];
17       uniq[n][0] = uniq[n][0] && uniq[*it][1];
18     } else {
19       dp[n][0] += dp[*it][0];
20       uniq[n][0] = uniq[n][0] && uniq[*it][0];
21     }
22     dp[n][1] += dp[*it][0];
23     uniq[n][1] = uniq[n][1] && uniq[*it][0];
24   }
25 }
26 
27 int main()
28 {
29   int N;
30   while (cin >> N && N != 0) {
31     map<string,int> m;
32     string s1;
33     cin >> s1;
34     m.insert(make_pair(s1, 0));
35     vector<vector<int> > g(N);
36     for (int i = 0; i < N-1; i++) {
37       string s2;
38       cin >> s1 >> s2;
39       if (!m.count(s1)) {
40         m.insert(make_pair(s1, m.size()));
41       }
42       if (!m.count(s2)) {
43         m.insert(make_pair(s2, m.size()));
44       }
45       g[m[s2]].push_back(m[s1]);
46     }
47 
48     vector<vector<int> > dp(N, vector<int>(2));
49     vector<vector<bool> > uniq(N, vector<bool>(2));
50     dfs(g, 0, dp, uniq);
51     int ans;
52     bool u;
53     if (dp[0][0] == dp[0][1]) {
54       ans = dp[0][0];
55       u = false;
56     } else if (dp[0][0] < dp[0][1]) {
57       ans = dp[0][1];
58       u = uniq[0][1];
59     } else {
60       ans = dp[0][0];
61       u = uniq[0][0];
62     }
63     cout << ans << ' ' << (u ? "Yes" : "No") << endl;
64   }
65   return 0;
66 }
poj/3342.cc