題目鏈接：https://uva.onlinejudge.org/external/12/1220.pdf

題意： 公司n個人，形成一個數狀結構，選出最大獨立集，并且看是否是唯一解。

分析：

d(i) 是 節點 i 的最優值， i 只有兩種決策，就是選和不選。 轉移方程：

d(i) = max {1+Σ₁d(j),Σ₂d(j)};?Σ₁是所有孫子節點，Σ₂是所有兒子節點。

那么狀態的定義d(i,0),節點 i 不選，d(i,1)，節點 i 選。

那么狀態轉移方程就是：

是否唯一 f(v,0) = 1 表示唯一， f(v,1) = 0 不唯一。

d(u,1) = sum{d(v,0)}（v是u的子節點），當所有 f(v,0) = 1,d(u,1) = 1;

d(u,0) = sum{max(d(v,0),d(v,1))}, if (d(v,0)==d(v,1)) f(u,0) = 0,取的對應的f()==0,f(u,0) = 0;

存樹形結構，一個較好的方式用鄰接表，每個字符串對應一個ID，可以用map<string,int>dict，有一個較好的函數，dict.count(s)，s字符串出現的次數。

#include <bits/stdc++.h> using namespace std;const int maxn = 200+5; int cnt; int n; vector<int> sons[maxn]; int d[maxn][2],f[maxn][2];map<string,int> dict;int ID(const string &s) {if(!dict.count(s)) dict[s] = cnt++;return dict[s]; }int dp(int u,int k) {f[u][k] = 1;d[u][k] = k;for(int i=0;i<sons[u].size();i++) {int v = sons[u][i];if(k==1) {d[u][1] +=dp(v,0);if(!f[v][0]) f[u][1] = 0;}else {d[u][0] +=max(dp(v,0),dp(v,1));if(d[v][0]==d[v][1]) f[u][k] = 0;else if(d[v][0]>d[v][1]&&!f[v][0]) f[u][k] = 0;else if(d[v][1]>d[v][0]&&!f[v][1]) f[u][k] = 0;}}return d[u][k]; }int main() {string s,s2;while(cin>>n>>s) {cnt = 0;dict.clear();for(int i=0;i<n;i++)sons[i].clear();ID(s);for(int i=0;i<n-1;i++) {cin>>s>>s2;sons[ID(s2)].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;if(d[0][1]>d[0][0]&&f[1][0]) unique = true;if(unique) printf("Yes\n");else printf("No\n");}return 0; } View Code

?

轉載于:https://www.cnblogs.com/TreeDream/p/6002006.html

總結

以上是生活随笔為你收集整理的Uva 1220，Hali-Bula 的晚会的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。