UVA1220PartyAtHailBula

xiaoxiao2021-02-28  104

//UVA1220PartyAtHailBula #include<cstdio> #include<cstring> #include<map> #include<algorithm> #include<iostream> #include<vector> using namespace std; const int MAXN = 200 + 5; vector<int> son[MAXN]; int f[MAXN][2], d[MAXN][2]; map<string, int> id; int cnt = 0, n; int ID(const string s) { if(!id.count(s)) id[s] = cnt++; return id[s]; } int dp(int i, int j) { d[i][j] = j;//此赋值具有一定的技巧性 f[i][j] = 1;//假设无重复 int sons = son[i].size(); for(int k = 0; k < sons; k++) { int v = son[i][k]; if(j == 1) {//i被选中了 d[i][j] += dp(v, 0); if(!f[v][0]) f[i][j] = 0; } else { d[i][j] += max(dp(v, 0), dp(v, 1)); int Unique = false; if(d[v][0] == d[v][1]) Unique = false; else if(d[v][0] > d[v][1] && f[v][0]) Unique = true; else if(d[v][1] > d[v][0] && f[v][1]) Unique = true; if(!Unique) f[i][j] = 0; } } return d[i][j]; } int main() { string s, s1; //freopen("UVA1220out.txt", "w", stdout); while(scanf("%d", &n) == 1 && n) { cnt = 0; for(int i = 0; i <= n; i++) son[i].clear(); id.clear(); cin >> s;//big boss int big_boss = ID(s); for(int i = 0; i < n - 1; i++) { cin >> s >> s1; son[ID(s1)].push_back(ID(s)); } printf("%d ", max(dp(0, 0), dp(0, 1))); bool Unique = false; if(d[0][0] > d[0][1] && f[0][0]) Unique = true; else if(d[0][1] > d[0][0] && f[0][1]) Unique = true; if(Unique) printf("Yes\n"); else printf("No\n"); } return 0; } /* 6 Jason Jack Jason Joe Jack Jill Jason John Jack Jim Jill 2 Ming Cho Ming 0 */ /* 10 Muo Mqb Ioh Ppk Vje Vje Muo Jna Vje Yei Aqx Ioh Yei Tuk Muo Aqx Rrb Rrb Jna */
转载请注明原文地址: https://www.6miu.com/read-48495.html

最新回复(0)