UVA-1220-Party at Hali-Bula
题意：
一个公司员工要举行聚会，要求任意一个人不能和他的直接上司同时到场，一个员工只有一个支系上司，现在求最多有多少人到场，并且方案是否唯一（紫书282页）
分析：
紫薯写的很清楚，而且也很基础，就不重复了，只做几点记录和总结
- 输入中输入的是名字，每个名字要和一个id对应，当然最容易想到的就是map。但是还需要注意一点，就是不能保证输入的顺序，也就是说如果首先输入的父节点之前没有出现过，那么就没办法获取到父节点的id。建树时要考虑输入数据的顺序（或者是重复输入的）
- 关于此题，因为要判断唯一性，所以不是单纯的树的最大独立点集问题。而新增的数组
f，则可以很方便的把唯一性的状态储存下来。
#define maxn 210
vector<int> v[maxn];
map<string,int> M;
int n;
int ans,res;
int dp[maxn][2],f[maxn][2];
void dfs(int u)
{
dp[u][0] = 0;
dp[u][1] = 1;
f[u][0] = f[u][1] = 1;
int l = v[u].size();
//树形dp基本框架
for(int i=0;i<l;i++)
{
int y = v[u][i];
dfs(y);
dp[u][1] += dp[y][0];
if(f[y][0]==0)f[u][1] = 0;
dp[u][0] += max(dp[y][0],dp[y][1]);
if(dp[y][0]==dp[y][1])f[u][0] = 0;
else if(dp[y][0]>dp[y][1]&&f[y][0]==0)f[u][0] = 0;
else if(dp[y][0]<dp[y][1]&&f[y][1]==0)f[u][0] = 0;
}
}
//获取对应id
int cnt;
int id(const string& str)
{
if(!M.count(str))
M[str] = ++cnt;
return M[str];
}
int main()
{
while(cin>>n)
{
if(n==0)break;
for(int i=1;i<=n;i++)
v[i].clear();
//ans储存人数，res保存是否唯一
ans = 0;res = 1;
M.clear();
cnt = 0;
string a,b;
cin>>a;
id(a);
//输入的坑点就在这里
for(int i=2;i<=n;i++)
{
cin>>a>>b;
v[id(b)].push_back(id(a));
//M[a] = i;这是之前错误的写法，因为我们不能保证M[b]一定存在。
//v[M[b]].push_back(M[a]);
}
dfs(1);
ans = max(dp[1][0],dp[1][1]);
if(dp[1][0]==dp[1][1]||(dp[1][0]>dp[1][1]&&f[1][0]==0)||(dp[1][0]<dp[1][1]&&f[1][1]==0))
res = 0;
printf("%d %s\n",ans,res==0?"No":"Yes");
}
return 0;
}
UVA-1218-Perfect Service
题意：
有n个机器组成的树形结构，要求一台服务器必须连接一台电脑，求使用的最少的服务器
分析
对于任意一个机器u，可以是服务器也可以不是服务器，由于有“不是服务器的机器必须恰好与一个服务器相邻”的条件，又由于它是一棵树，所以我们借用每个节点的父节点，来表示状态。即分为三种情况
- u是服务器。那么与u管联的任何机器可以是服务器也可以不是
- u不是服务器，u的父节点是服务器。那么u的所有子节点都不是服务器
- u不是服务器，u的父节点不是服务器。那么u必须恰好有一个子节点是服务器
动态转移：
d[u][0] = sum{ min(d[v][0],d[v][1])}
d[u][1] = sum{d[v][2]}
d[u][2] = min(d[u][1]-d[v][2]+d[v][0])
第三个含义是这样的：因为要求v是服务器的情况的最小值，并且u的其他子节点都不是服务器。d[u][0]保存了u子节点都不是服务器的最优解，d[v][2]保存了v不是服务器的最优解，d[v][0]保存了v是服务器的最优解。所以有上述式子可得d[u][2]的最优解
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3fffffff
#define maxn 10010
vector<int> v[maxn];
int n,ans;
int d[maxn][3];
void dp(int x,int p)
{
d[x][0] = 1;
d[x][1] = 0;
d[x][2] = maxn;
int l = v[x].size();
for(int i=0;i<l;i++)
{
int y = v[x][i];
if(y==p)continue;
dp(y,x);
d[x][0] += min(d[y][0],d[y][1]);
d[x][1] += d[y][2];
}
//因为计算d[x][2]要用到d[x][1]，而d[x][1]是累加计算，所以要分开两次遍历
for(int i=0;i<l;i++)
{
int y = v[x][i];
if(y==p)continue;
d[x][2] = min(d[x][2],d[x][1]-d[y][2]+d[y][0]);
}
}
int main()
{
while(~scanf("%d",&n)&&n!=-1)
{
if(n==0)continue;
for(int i=1;i<=n;i++)
v[i].clear();
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dp(1,0);
//最后这里的坑点，想一想为什么没有d[1][1]呢？
ans = min(d[1][0],d[1][2]);
cout<<ans<<endl;
}
return 0;
}