UVA - 1220 Party at Hali-Bula （树形DP）

有 n 个员工，n-1个从属关系。

不能同时选择某个员工和他的直接上司，问最多可以选多少人，以及选法是否唯一。

树上的最大独立集问题。只不过多了一个判断唯一性。

dp[u][0]表示不选这个点的状态，dp[u][1]表示选这个点的状态。

如果不选 u，那么 u点状态是由 dp[v][0] 或者 dp[v][1]，大的那个点转移过来，唯一性同时也转移。

如果选 u ，那么 u点状态是由所有的 dp[v][0] 转移过来，所以只有所有的 dp[v][0]状态的都唯一时，dp[u][1]才唯一。

另外，我一直 WA 的原因在于给员工编号的时候没有判断有没有出现过，默认每行的第一个都是没有出现过的。瞎改了好久。

吸取教训。

#include <bits/stdc++.h>

using namespace std;

#define maxn 100010

vector<int> son[maxn], fa[maxn];

int same[maxn], dp[maxn][], f[maxn][];

void DP(int k)

{

        dp[k][] = , dp[k][] = ;

        f[k][] = , f[k][] = ;

        for (int i = ; i < son[k].size(); i++)

        {

                int v = son[k][i];

                DP(v);

                dp[k][] += max(dp[v][], dp[v][]);

                if (dp[v][] == dp[v][]) f[k][] = ;

                if (dp[v][] > dp[v][] && f[v][] == ) f[k][] = ;

                if (dp[v][] < dp[v][] && f[v][] == ) f[k][] = ;

                dp[k][] += dp[v][];

                if (f[v][] == ) f[k][] = ;

        }

}

void init(int n)

{

        for (int i = ; i < n; i++)

                son[i].clear();

        memset(f, , sizeof());

}

int main()

{

        int n;

        while(~scanf("%d", &n) && n)

        {

                init(n);

                map<string, int> idx;

                string s;

                cin >> s;

                idx[s] = ;

                int id = ;

                for (int i = ; i <= n-; i++)

                {

                        string x, y;

                        cin >> x >> y;

                        if (!idx.count(x))

                            idx[x] = ++id;

                        if (!idx.count(y))

                            idx[y] = ++id;

                        son[idx[y]].push_back(idx[x]);

                }

                DP();

                int uniq = ;

                if (dp[][] > dp[][] && f[][] == ) uniq = ;

                        else if (dp[][] < dp[][] && f[][] == ) uniq = ;

                        else if (dp[][] == dp[][]) uniq = ;

                printf("%d %s\n", max(dp[][], dp[][]), uniq ? "Yes":"No");

        }

}

巴特西

UVA - 1220 Party at Hali-Bula （树形DP）

最新文章

热门文章