Party at Hali-Bula UVA
Party at Hali-Bula
题意：选一个公司的人去参加晚会，要求不能选有直接上下级关系的人，问最多选多少人去，并判断方案是否唯一。
树的最大独立集，并判断是否唯一。
d[u][1]表示选u，d[u][0]表示不选u
f[u][1]==1表示选u的情况下唯一，f[u][1]==0表示不唯一
f[u][0]为不选u的情况下的唯一性
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=220; 5 map<string,int> m; 6 int n; 7 struct edge{ 8 int v,nex; 9 }e[maxn]; 10 int head[maxn]; 11 int cnt=0; 12 void add(int u,int v){ 13 e[cnt].v=v; 14 e[cnt].nex=head[u]; 15 head[u]=cnt++; 16 } 17 string s1,s2; 18 int d[maxn][2],f[maxn][2]; 19 void dfs(int u){ 20 int i=head[u]; 21 if(i==-1){ 22 d[u][0]=0; 23 f[u][0]=1; 24 d[u][1]=1; 25 f[u][1]=1; 26 return ; 27 } 28 f[u][1]=f[u][0]=1; 29 for(;i!=-1;i=e[i].nex){ 30 int v=e[i].v; 31 dfs(v); 32 d[u][0]+=max(d[v][1],d[v][0]); 33 d[u][1]+=d[v][0]; 34 if(!f[v][0]) f[u][1]=0; 35 if(d[v][1]==d[v][0]) f[u][0]=0; 36 if(d[v][1]>d[v][0]&&f[v][1]==0) f[u][0]=0; 37 if(d[v][0]>d[v][1]&&f[v][0]==0) f[u][0]=0; 38 } 39 d[u][1]++; 40 return ; 41 } 42 int main(){ 43 while(scanf("%d",&n)&&n){ 44 m.clear(); 45 int id=2; 46 cnt=0; 47 memset(head,-1,sizeof(head)); 48 memset(d,0,sizeof(d)); 49 memset(f,0,sizeof(f)); 50 cin>>s1; 51 m[s1]=1; 52 for(int i=1;i<n;i++){ 53 cin>>s1>>s2; 54 if(!m[s1]) m[s1]=id++; 55 if(!m[s2]) m[s2]=id++; 56 add(m[s2],m[s1]); 57 } 58 dfs(1); 59 int ans,flag=1; 60 if(d[1][1]>d[1][0]){ 61 ans=d[1][1]; 62 if(f[1][1]) flag=1; 63 else flag=0; 64 } 65 else if(d[1][1]<d[1][0]){ 66 ans=d[1][0]; 67 if(f[1][0]) flag=1; 68 else flag=0; 69 } 70 else ans=d[1][1],flag=0; 71 printf("%d %s ",ans,flag?"Yes":"No"); 72 } 73 }