本文共 2673 字，大约阅读时间需要 8 分钟。
还是简单的树形dp，不过要判断最优解是否有多种。
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int N = 201; 8 int head[N]; 9 int dp[N][2]; 10 bool flag[N][2]; 11 int n, e, cnt; 12 map mp; 13 14 struct Edge 15 { 16 int v, next; 17 } edge[N]; 18 19 void addEdge( int u, int v ) 20 { 21 edge[e].v = v; 22 edge[e].next = head[u]; 23 head[u] = e++; 24 } 25 26 void dfs( int u ) 27 { 28 dp[u][0] = 0, dp[u][1] = 1; 29 for ( int i = head[u]; i != -1; i = edge[i].next ) 30 { 31 int v = edge[i].v; 32 dfs(v); 33 dp[u][1] += dp[v][0]; 34 if ( flag[v][0] ) 35 { 36 flag[u][1] = true; 37 } 38 if ( dp[v][0] > dp[v][1] ) 39 { 40 dp[u][0] += dp[v][0]; 41 if ( flag[v][0] ) 42 { 43 flag[u][0] = true; 44 } 45 } 46 else if ( dp[v][0] < dp[v][1] ) 47 { 48 dp[u][0] += dp[v][1]; 49 if ( flag[v][1] ) 50 { 51 flag[u][0] = true; 52 } 53 } 54 else 55 { 56 dp[u][0] += dp[v][0]; 57 flag[u][0] = true; 58 } 59 } 60 } 61 62 char str1[N], str2[N]; 63 64 int main () 65 { 66 while ( scanf("%d", &n), n ) 67 { 68 e = 0; 69 cnt = 1; 70 memset( head, -1, sizeof(head) ); 71 mp.clear(); 72 scanf("%s", str1); 73 mp[str1] = cnt++; 74 for ( int i = 1; i < n; i++ ) 75 { 76 scanf("%s%s", str1, str2); 77 if ( mp.count(str1) == 0 ) 78 { 79 mp[str1] = cnt++; 80 } 81 if ( mp.count(str2) == 0 ) 82 { 83 mp[str2] = cnt++; 84 } 85 addEdge( mp[str2], mp[str1] ); 86 } 87 memset( flag, false, sizeof(flag) ); 88 dfs(1); 89 if ( dp[1][0] > dp[1][1] ) 90 { 91 printf("%d", dp[1][0]); 92 if ( !flag[1][0] ) 93 printf(" Yes\n"); 94 else 95 printf(" No\n"); 96 } 97 else if ( dp[1][1] > dp[1][0] ) 98 { 99 printf("%d", dp[1][1]);100 if ( !flag[1][1] )101 printf(" Yes\n");102 else103 printf(" No\n");104 }105 else106 {107 printf("%d No\n", dp[1][0]);108 }109 }110 return 0;111 }
转载于:https://www.cnblogs.com/huoxiayu/p/4660819.html