Perfect Service UVA - 1218
树形DP
题目描述：求最少的服务器，使得其他不是服务器的计算机恰好和一台服务器计算机相邻。
解题分析：定义dp[u][0] u是服务器，每个子节点可以使服务器也可以不是。
dp[u][0] = sum(min(dp[v][0],dp[v][1])).
dp[u][1] u不是服务器,但u的父亲是服务器，所以u的所有子节点都不是服务器。
dp[u][1] = sum(dp[v][2]).
dp[u][2],u和u的父亲都不是服务器，所以u的儿子中必须恰好有一个儿子是服务器。
dp[u][2] = min(dp[v][0] + sum(others dp[v][2])).如果遍历每一个结点作为选定的服务器儿子，那么时间复杂度将会是k^2，k是子节点的个数。但实际上可以不用这样重复计算，
因为sum（dp[v][2]）已经在dp[u][1]里面给计算过了，所以可以利用上面的结果。则
dp[u][2] = min(dp[u][1] - dp[v][1] + dp[v][0]).
第一遍写的代码：
有两点不太明白，一直WA，第一个是在边界处理上，如果u没有子节点的话,dp[u][2] = maxn, 而我之前写的是dp[u][2] = 0;
第二点不明白的是:为什么dp[u][2]的初始化为0x3f3f3f3f就会WA呢，感觉没什么问题啊，哦，明白了,如果初始化为0x3f3f3f3f的话，n个0x3f3f3f3f相加就会数据溢出了。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 10000 + 10;
const int INF = 0x3f3f3f3f;
int par[maxn];
vector<int> temp[maxn];
vector<int> son[maxn];
int dp[maxn][3];
int n;
int dfs(int u)
{
if(son[u].size() == 0)
{
dp[u][0] = 1;
dp[u][1] = 0;
dp[u][2] = maxn;
}
else
{
for(int i = 0; i < son[u].size(); i++)
{
dfs(son[u][i]);
}
int sum0 = 0,sum1 = 0;
for(int i = 0; i < son[u].size(); i++)
{
int v = son[u][i];
sum0 += min(dp[v][1],dp[v][0]);
sum1 += dp[v][2];
}
dp[u][0] = sum0 + 1;
dp[u][1] = sum1;
for(int i = 0; i < son[u].size(); i++)
{
int v = son[u][i];
dp[u][2] = min(dp[u][2],dp[u][1]-dp[v][2] + dp[v][0]);
}
}
}
void build_tree(int u,int p)
{
for(int i = 0;i < temp[u].size(); i++)
{
int v = temp[u][i];
if(v != p)
{
par[v] = u;
build_tree(v,u);
}
}
}
int main()
{
while(cin >> n && n!= -1)
{
if(n == 0) continue;
for(int i = 0; i <= n; i++)
{
son[i].clear();
temp[i].clear();
par[i] = i;
dp[i][2] = maxn;
}
int x,y;
for(int i = 0; i < n-1; i++)
{
cin >> x >> y;
temp[y].push_back(x);
temp[x].push_back(y);
}
int root = 1;
par[root] = 0;
build_tree(root,0);
for(int i = 1; i <= n; i++)
{
son[par[i]].push_back(i);
}
dfs(1);
printf("%d\n",min(dp[root][0],dp[root][2]));
}
return 0;
}
后来发觉有大佬直接对无根树处理，只需要递归的时候判断一下是不是父节点就行
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 10000 + 10;
vector <int> graph[maxn];
int dp[maxn][3];
int n;
void dfs(int u,int fa)
{
dp[u][0] = 1;
dp[u][1] = 0;
dp[u][2] = maxn;
for(int i = 0; i < graph[u].size(); i++)
{
int v = graph[u][i];
if(v != fa)
{
dfs(v,u);
}
}
for(int i = 0; i < graph[u].size(); i++)
{
int v = graph[u][i];
if(v == fa) continue;
dp[u][0] += min(dp[v][0],dp[v][1]);
dp[u][1] += dp[v][2];
}
for(int i = 0; i < graph[u].size(); i++)
{
int v = graph[u][i];
if(v == fa) continue;
dp[u][2] = min(dp[u][2],dp[u][1] - dp[v][2] + dp[v][0]);
}
}
int main()
{
while(cin >> n && n != -1)
{
if(n == 0) continue;
for(int i = 0; i <= n; i++)
{
dp[i][2] = maxn;
graph[i].clear();
}
for(int i = 0; i < n-1; i++)
{
int x,y;
scanf("%d %d",&x,&y);
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs(1,0);
printf("%d\n",min(dp[1][0],dp[1][2]));
}
return 0;
}
投递腾讯等公司10个岗位 >
美团公司氛围 1901人发布
