网友投稿 273 2022-11-01
UVA 1220 Party at Hali-Bula——dp
紫书P282讲得很明白
#include #include #include #include #include #include #include using namespace std;const int maxn = 500;int n, tot = 0;vector G[maxn];map m;bool judge[maxn][2];int dp[maxn][2];void dfs(int u) { if (G[u].size() == 0) { dp[u][0] = 0; dp[u][1] = 1; judge[u][0] = judge[u][1] = true; return; } dp[u][1] = 1; dp[u][0] = 0; judge[u][1] = judge[u][0] = true; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; dfs(v); dp[u][1] += dp[v][0]; judge[u][1] &= judge[v][0]; if (dp[v][0] > dp[v][1]) { dp[u][0] += dp[v][0]; judge[u][0] &= judge[v][0]; } else if (dp[v][0] < dp[v][1]) { dp[u][0] += dp[v][1]; judge[u][0] &= judge[v][1]; } else { dp[u][0] += dp[v][0]; judge[u][0] = false; } }}int main() { //freopen("out.txt", "w", stdout); while (~scanf("%d", &n) && n) { for (int i = 1; i <= n; i++) G[i].clear(); m.clear(); tot = 0; string s1, s2; cin >> s1; if (!m[s1]) m[s1] = ++tot; for (int i = 1; i <= n - 1; i++) { cin >> s1 >> s2; if (!m[s1]) m[s1] = ++tot; if (!m[s2]) m[s2] = ++tot; G[m[s2]].push_back(m[s1]); } dfs(1); bool res; int ans; if (dp[1][0] > dp[1][1]) ans = dp[1][0], res = judge[1][0]; else if (dp[1][0] < dp[1][1]) ans = dp[1][1], res = judge[1][1]; else ans = dp[1][0], res = false; printf("%d ", ans); if (res) printf("Yes\n"); else printf("No\n"); } return 0;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~