原题链接:UVA1218 完美的服务 Perfect Service
题目大意
给定一个(n)个点的无向树,现要在某些点上设立服务器.每个不是服务器的点必须只恰好跟一个是服务器的点相连.问最少要放置几个服务器.
数据范围
(1 leq n leq 10000)
注意正无穷不要设置0x3f3f3f3f,据说有类似菊花图爆数据的.
思路
这是一个比较明显而且套路的树形DP的模型.先划分一下状态,这个题的限制条件是一个不是服务器的点只能和一个服务器连接,服务器之间连几个无所谓.那么比较容易想到这样的划分:(f[u][j])表示以(u)为根的子树里,(j=0)为(u)是服务器,他的儿子是不是无所谓;(j=1)为(u)不是服务器,但是(u)的父节点是服务器,那么他的儿子必然不可能是服务器;(j=2)表示(u)和他父节点都不是服务器,但是如果他不存在父节点,那就不管,那么(u)只有一个儿子是服务器.
这里一定要注意是如果有父节点才会要求他不是一个服务器,如果他没有父节点,但是本身也不是服务器,那么其实也是满足定义的.而(f[u][1])是强调有父节点,且必须是服务器的,不然会和状态矛盾.
入口:(f[u][0] = 1)是因为要设置自己是服务器.(f[u][1]=0)和(f[u][2]=正无穷)跟实际状态转移有关.
转移:
①(f[u][0])
因为如果(u)是一个服务器,那么(u)的儿子是不是服务器是无所谓的,所以直接取较小的就可以了.(f[u][0] = sumlimits_{vin subtree(u)} min(f[v][0],f[v][1]) + 1).这里的(1)一开始就加了,代码里可以不写.
②(f[u][1])
这个时候由于(u)不是服务器,但是他的父节点是,又因为每个不是服务器的点只能和一个服务器相连,所以他的儿子(v)都不能是服务器,也就是说,对于儿子此时的状态其实就是(f[v][2]),自己不能选,父节点(u)也不能选,直接拿来用就可以了.(f[u][1] = sumlimits_{vin subtree(u)} f[v][2])
③(f[u][2])
这个状态的计算看起来就很奇怪,如果从定义出发的话计算会成平方级,也就是跟儿子的个数的平方级有关的复杂度.显然是不行的,考虑从现有的状态里直接计算出这个状态:因为现在是只有一个(v)可以用,所以不妨先把所有的(f[v][2])加起来,然后在里面随便抠一个(v),把他变成服务器的代价算出来,实际上就是加一个(f[v][0])再减去一个(f[v][1]).因为你要把一开始所有都没选上的状态里那个(f[v][2])给去掉,再加上他作为服务器往下的代价.而且联系前面的内容,由于(f[u][1]=sumlimits_{vin subtree(u)} f[v][2])所以这里的表达是可以推出来是(f[u][2] = {min}_{vin subtree(u)}(f[u][1] - f[v][2] - f[v][0]))
出口:答案一共有两种,一种是(f[root][0]),一种是(f[root][2]),其中根root可以任选,两种取最小值就可以了.没有(f[root][1])的原因是这种情况其实并不合法,因为对于这个(root)来说他的形态应该是没有父节点的.
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10005,M = 2 * N;
int edge[M],succ[M],ver[N],idx;
int n,f[N][3];
void add(int u,int v)
{
edge[idx] = v;
succ[idx] = ver[u];
ver[u] = idx++;
}
void dfs(int u,int fa)
{
f[u][0] = 1;f[u][2] = 10010;f[u][1] = 0;
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa) continue;
dfs(v,u);
f[u][0] += min(f[v][0],f[v][1]);
f[u][1] += f[v][2];
}
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa) continue;
f[u][2] = min(f[u][2],f[u][1] + f[v][0] - f[v][2]);
}
}
int main()
{
while(scanf("%d",&n) == 1)
{
memset(ver,-1,sizeof ver);idx = 0;
if(n == 0) scanf("%d",&n);
if(n == -1) break;
for(int i = 1;i < n;++i)
{
int u,v;scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(1,-1);
printf("%d
",min(f[1][0],f[1][2]));
}
return 0;
}