树的最大独立集（UVA1220）Party at Hali

独立集（UVA1220）Party at Hali"/>

树的最大独立集（UVA1220）Party at Hali

对于一颗n个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集），然后输入n-1条无向边，输出一个最大独立集（如果有多解输出任意一组）。

• 任选一个根r，d(i)表示以i为根结点的子树的最大独立集大小，结点i有两种决策，选与不选，如果不选i，问题变成了所有儿子的值相加，如果选i,问题变成了所有孙子的值相加再加1，即d(i)=max(1+Σd(j)，Σd(k));j为i的孙子(gs[i])，k为i的儿子(s[i])。
• 实现时可以从s[i]与gs(i)的元素去找i，即当计算出一个d(i)后，用它去更新其父亲结点和祖父结点的累加值。(以上来自紫书)。
• -关于UVA 1220 Party at Hali-Bula：d(i,0)表示以i为根结点的子树在选择i的情况下的最大独立集，d(i,1)表示以i为根结点的子树在不选择i的情况下的最大独立集，则有d(i,1)=Σmax(d(s[i],0),d(s[i],1));d(i,0)=Σd(s[i],1);关于方案的唯一性（自上而下考虑更容易），在选择i点时其所有儿子唯一i才唯一，不选择i的情况下如果d(s[i],0)=d(s[i],1)或者两者max的那一项不唯一i才不唯一；

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<fstream>
using namespace std;
int d[205][2],n,num,tmp;//0:取,1：不取 
bool onl[205][2],used[205];//1:不唯一 
struct tree{int s,f;
}t[205];
int main()
{
//	freopen("1.txt","w",stdout);while(cin>>n&&n){string s1,s2;num=0;map<int,string>m;map<string,int>q;cin>>s1;m[++num]=s1;q[s1]=1;for(int i=1;i<n;i++){cin>>s1>>s2;if(!q[s1]){m[++num]=s1;q[s1]=num;}if(!q[s2]){m[++num]=s2;q[s2]=num;}t[q[s2]].s+=1;t[q[s1]].f=q[s2];}tmp=n;for(int i=1;i<=n;i++)d[i][0]=1;while(tmp!=0){for(int i=1;i<=n;i++){if(!t[i].s&&!used[i]){used[i]=1;tmp--;t[t[i].f].s--;if(t[i].f){if(d[i][0]==d[i][1])onl[t[i].f][1]=1;if(d[i][0]>d[i][1]&&onl[i][0]||d[i][0]<d[i][1]&&onl[i][1])onl[t[i].f][1]=1;if(onl[i][1])onl[t[i].f][0]=1;d[t[i].f][1]+=max(d[i][0],d[i][1]);d[t[i].f][0]+=d[i][1];}}}}if(d[1][0]>d[1][1])cout<<d[1][0]<<' '<<(onl[1][0]==1?"No":"Yes")<<endl;else if(d[1][0]<d[1][1])cout<<d[1][1]<<' '<<(onl[1][1]==1?"No":"Yes")<<endl;elsecout<<d[1][1]<<' '<<"No"<<endl;memset(t,0,sizeof(t));memset(used,0,sizeof(used));memset(onl,0,sizeof(onl));memset(d,0,sizeof(d)); }return 0;}