UVA - 1218 Perfect Service (树形dp)

柔光的暖阳◎ 2021-12-18 08:05 154阅读 0赞

## 题意：有n台电脑，互相以无根树的方式连接，现要将其中一部分电脑作为服务器，且要求每台电脑必须连接且只能连接一台服务器(不包括作为服务器的电脑)，求最少需要多少台电脑作为服务器。 ##

## 分析：典型的树形dp问题，那么我们来建立模型。  ##

## d\[u\]\[0\]：u是服务器，则每个子结点可以是服务器也可以不是。 ##

## d\[u\]\[1\]：u不是服务器，但u的父亲是服务器，这意味着u的所有子结点都不是服务器。 ##

## d\[u\]\[2\]：u和u的父亲都不是服务器。这意味着u恰好有一个儿子是服务器。 ##

## 状态转移方程分析： ##

## d\[u\]\[0\]：由于它已经是服务器了，所以子结点可以是也可以不是，选择小的，d\[u\]\[1\]=sum\{min(d\[v\]\[0\],d\[v\]\[1\])\}+1。1代表它自身这个服务器。 ##

## d\[u\]\[1\]：u的父亲是服务器，那么与它相连的就不可能是服务器了，此时很简单，d\[u\]\[1\]=sum(d\[v\]\[2\])。 ##

## d\[u\]\[2\]：子结点有且仅有一个服务器，也就是说d\[u\]\[2\]=min(d\[u\]\[2\],d\[v1\]\[2\]+d\[v2\]\[2\].....+d\[v\]\[0\])。由于前面已经算出了所有子结点的d\[v\]\[2\]和，所以这里可以简化为d\[u\]\[2\]=min(d\[u\]\[2\],d\[u\]\[1\]-d\[v\]\[2\]+d\[v\]\[0\])。 ##

## 注意：溢出问题。 ##

## 刘汝佳代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 10000 + 5;
    const int INF = 1000000000;
    
    vector<int> G[maxn], vertices;
    int p[maxn], d[maxn][3];
    
    // build a rooted tree and dfs sequence
    void dfs(int u, int fa)
    {
        vertices.push_back(u);
        p[u] = fa;
        for(int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            if(v != fa) dfs(v, u);
        }
    }
    
    int main()
    {
        int n;
        while(scanf("%d", &n) == 1)
        {
            for(int i = 0; i < n; i++) G[i].clear();
            for(int i = 0; i < n-1; i++)
            {
                int u, v;
                scanf("%d%d", &u, &v);
                u--;
                v--;
                G[u].push_back(v);
                G[v].push_back(u);
            }
            vertices.clear();
            dfs(0, -1);
            for(int i = vertices.size()-1; i >= 0; i--)
            {
                int u = vertices[i];
                d[u][0] = 1;
                d[u][1] = 0;
                for(int j = 0; j < G[u].size(); j++)
                {
                    int v = G[u][j];
                    if(v == p[u]) continue;
                    d[u][0] += min(d[v][0], d[v][1]); // u is server
                    d[u][1] += d[v][2]; // u is not server, u's father is server
                    if(d[u][0] > INF) d[u][0] = INF; // avoid overflow!
                    if(d[u][1] > INF) d[u][1] = INF;
                }
                d[u][2] = INF;
                for(int j = 0; j < G[u].size(); j++)
                {
                    int v = G[u][j];
                    if(v == p[u]) continue;
                    d[u][2] = min(d[u][2], d[u][1] - d[v][2] + d[v][0]); // neither u or father is server
                }
            }
            printf("%d\n", min(d[0][0], d[0][2]));
            scanf("%d", &n);
        }
        return 0;
    }