UVa 1220 Party at Hali-Bula （树形DP，最大独立集）

向右看齐 2021-12-18 07:39 170阅读 0赞

## 题意：公司有 n 个人形成一个树形结构，除了老板都有唯一的一个直系上司，要求选尽量多的人，但不能同时选一人上和他的直系上司，问最多能选多少人，并且是不是唯一的方案。 ##

## 分析：设d(u,0),f(u,0)是以u为根的子树中不选u点时能够得到的最大人数和表示方案唯一【f(u,0)表示方案唯一，f(u,1)表示方案不唯一】，d(u,1),f(u,1)表示选u点时能够得到的最大人数和表示方案唯一。转移方程也有两种，一种是d(u,1)的计算，因为选了u点，所以u的直接子节点都不能选，因此d(u,1)=sum\{d(v,0)|v是u的直接子节点不能选\}，当且仅当所有的f(v,0)=1时f(u,1)才是1【方案唯一】。另一种是d(u,0)的计算，因为u点没有被选择所以u的直接子节点可选或不选，即d(u,0)=sum\{ max( d(v,0),d(v,1) ) \}当d(v,0)=d(v,1)即选和不选子节点的情况一样则方案不唯一，当d(v,0)>d(v,1)且f(v,0)=0时方案不唯一，d(v,1)>d(v,0)且f(v,1)=0时方案也不唯一。 ##

## 刘汝佳代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 200 + 5;
    int cnt;
    vector<int> sons[maxn];
    int n, d[maxn][2], f[maxn][2];
    
    map<string, int> dict;
    int ID(const string& s)
    {
        if(!dict.count(s)) dict[s] = cnt++;
        return dict[s];
    }
    
    int dp(int u, int k)
    {
        f[u][k] = 1;
        d[u][k] = k;
        for(int i = 0; i < sons[u].size(); i++)
        {
            int v = sons[u][i];
            if(k == 1)///选u节点
            {
                d[u][1] += dp(v, 0);
                if(!f[v][0]) f[u][1] = 0;///不选v节点的选法不唯一 父节点u选法也不唯一
            }
            else///不选u节点
            {
                d[u][0] += max(dp(v, 0), dp(v, 1));
                if(d[v][0] == d[v][1]) f[u][k] = 0;///当前节点的子节点选或者不选都一样就不唯一
                else if(d[v][0] > d[v][1] && !f[v][0]) f[u][k] = 0;///不选当前节点的子节点(v)的结果比选了要大，并且不选v节点的方案不唯一
                else if(d[v][1] > d[v][0] && !f[v][1]) f[u][k] = 0;///选当前节点的子节点(v)的结果比不选要大，并且选v节点的方案不唯一
                ///大的（要选中的）选法不唯一
            }
        }
        return d[u][k];
    }
    
    int main()
    {
        string s, s2;
        while(cin >> n >> s)
        {
            cnt = 0;
            dict.clear();
            for(int i = 0; i < n; i++) sons[i].clear();
            ID(s);
            for(int i = 0; i < n-1; i++)
            {
                cin >> s >> s2;
                sons[ID(s2)].push_back(ID(s));
            }
            printf("%d ", max(dp(0, 0), dp(0, 1)));///根节点选或者不选
            bool unique = false;
            if(d[0][0] > d[0][1] && f[0][0]) unique = true;
            if(d[0][1] > d[0][0] && f[0][1]) unique = true;
            if(unique) printf("Yes\n");
            else printf("No\n");
        }
        return 0;
    }