Uva 1220 Party at Hali

Uva 1220 Party at Hali"/>

Uva 1220 Party at Hali

题目大意：

给一个图，要求相邻节点不能同时选择，求最多能选出多少个节点，其次，判断最大节点数的情况是否唯一。

思路：

即求最大独立子集。在此基础上再判断情况唯一就行。

反思：

起初写了一个暴力判断情况唯一的，再一个节点下枚举判断每一个子节点是否情况唯一。这个代码再poj和hdoj上都过了，再uva上超时了，索性照着紫书上的方法再开一个vis数组再做一次dp。紫书开了一个二维数组a[i][0/1]来表示i节点选或不选得到的结果。如果不开二维数组的话，也可以开两个数组s[i]，gs[i]，分别记录子节点的答案和孙子节点的答案，同时需要开一个f[i]数组来记录i节点的父节点，稍显繁琐。本着简洁清楚的原则至上，开一个二维数组更好维护。就思路而言，如果判断一个题目是最大独立集问题，那么每个点有两个最基本的状态，即选或者不选，同时维护一些信息。

代码（暴力判断唯一性）

#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=200;map<string,int> m;
vector<int> v[MAXN+5];
char name[MAXN+5],na[MAXN+5];//string name,na;
int n,d[MAXN+5],s[MAXN+5],gs[MAXN+5],f[MAXN+5];
bool vis[MAXN+5];
bool ans=0;void dfs(int now,int fa){f[now]=fa;for(int i=0;i<v[now].size();i++){dfs(v[now][i],now);}if(s[now]==gs[now]+1)vis[now]=1;int c,l,le;if(!vis[now]&&s[now]>gs[now]+1){l=v[now].size();for(int i=0;i<l;i++){if(vis[v[now][i]]){vis[now]=1;break;}}}if(!vis[now]&&s[now]<gs[now]+1){le=v[now].size();for(int i=0;i<le;i++){c=v[now][i];l=v[c].size();for(int j=0;j<l;j++){if(vis[v[c][j]]){vis[now]=1;break;}}if(vis[now])break;}}d[now]=max(s[now],gs[now]+1);if(f[now]!=0)s[fa]+=d[now];if(f[fa]!=0)gs[f[fa]]+=d[now];
}
int main()
{//freopen("1.txt","r",stdin);//freopen("2.txt","w",stdout);int cnt;while(~scanf("%d",&n)&&n){ans=0;cnt=1;scanf("%s",name);m[name]=cnt++;for(int i=1;i<n;i++){scanf("%s%s",name,na);//cin>>name>>na;if(!m.count(name))m[name]=cnt++;if(!m.count(na))m[na]=cnt++;v[m[na]].push_back(m[name]);}dfs(1,0);printf("%d ",d[1]);if(vis[1]) printf("No\n");else printf("Yes\n");for(int i=0;i<=n;i++){d[i]=0;s[i]=0;gs[i]=0;f[i]=0;vis[i]=0;v[i].clear();}m.clear();}
}

代码（dp判断唯一性）

#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;vector<int> v[210];
map<string,int> m;
char a[210],b[210];
int ans[210][2];
bool vis[210][2];void dfs(int now){ans[now][1]=1;for(int i=0;i<v[now].size();i++){dfs(v[now][i]);int s=v[now][i];ans[now][1]+=ans[s][0];vis[now][1]|=vis[s][0];ans[now][0]+=max(ans[s][0],ans[s][1]);if(ans[s][1]==ans[s][0])vis[now][0]=1;else if(ans[s][1]>ans[s][0])vis[now][0]|=vis[s][1];else if(ans[s][0]>ans[s][1])vis[now][0]|=vis[s][0];}
}
int main()
{int t,cnt;while(~scanf("%d",&t)&&t){scanf("%s",a);cnt=1;m[a]=cnt++;for(int i=1;i<t;i++){scanf("%s%s",a,b);if(!m.count(a))m[a]=cnt++;if(!m.count(b))m[b]=cnt++;v[m[b]].push_back(m[a]);}dfs(1);printf("%d ",max(ans[1][0],ans[1][1]));if(ans[1][0]>ans[1][1]){if(vis[1][0]) puts("No");else puts("Yes");}else if(ans[1][0]<ans[1][1]){if(vis[1][1]) puts("No");else puts("Yes");}else if(ans[1][0]==ans[1][1])puts("No");m.clear();for(int i=0;i<=t;i++){v[i].clear();ans[i][1]=ans[i][0]=0;vis[i][0]=vis[i][1]=0;}}
}