UVa 1218 - Perfect Service（树形DP）

发表于 分类于 ， Disqus：

给出一个计算机网络，选取其中给一部分作为服务器，问最少选择几个服务器。
一共有三种状态：
1、 d [ u ] [ 0 ] ：u是服务器，每个子结点可以是也可以不是。
2、 d [ u ] [ 1 ] ：u不是服务器，但u的父亲是，u的子结点都不是服务器。
3、 d [ u ] [ 2 ] ：u和u的父亲都不是服务器，u的子结点恰有一个是服务器。
三种状态的转移：
d [ u ] [ 0 ] = ∑ m i n ( d [ v ] [ 0 ] , d [ v ] [ 1 ] ) + 1 。
d [ u ] [ 1 ] = ∑ d [ v ] [ 2 ] 。
d [ u ] [ 2 ] = m i n ( d [ u ] [ 1 ] − d [ v ] [ 2] + d [ v ] [ 0 ] ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=10010;
vector<int> g[maxn];
int d[maxn][3];
int vis[maxn];
int dp(int u){
    vis[u]=1;
    d[u][0]=1,d[u][1]=0,d[u][2]=maxn;
    queue<int> q;
    for(int i=0;i<g[u].size();++i)
        if(!vis[g[u][i]]){
            dp(g[u][i]);
            q.push(g[u][i]);
            d[u][0]+=min(d[g[u][i]][0],d[g[u][i]][1]);
            d[u][1]+=d[g[u][i]][2];
        }
    while(!q.empty()){
        d[u][2]=min(d[u][2],d[u][1]-d[q.front()][2]+d[q.front()][0]);
        q.pop();
    }
    return 0;
}

int main(){
    int n;
    while(~scanf("%d",&n)&&n!=-1){
        if(!n) continue;
        for(int i=1;i<=n;++i) g[i].clear();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;++i){
            int u,v;scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dp(1);
        printf("%d\n",min(d[1][0],d[1][2]));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章