紫书例题 9-13 UVa 1220 （最大独立子集）

这里的状态定义的非常的巧妙，d(i, 1)表示以i为根节点且选i的子树的最大独立子集

d(i, 0)表示以i为根节点且不选i的子树的最大独立子集

d(i, 1) = sum{ d(v, 0) | v是i的儿子}

d(i, 0) = sum{ max(d(v, 0), d(v, 1)) | v是i的儿子}

答案为 max（d(0, 0), d(0, 1)）

至于唯不唯一，很好推，当子树中有一个是不唯一的，那么当前节点就不唯一，或者有两个子树答案是一样的，也是不唯一的。

#include<cstdio>

#include<string>

#include<iostream>

#include<algorithm>

#include<vector>

#include<map>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 212;

vector<int> son[MAXN];

int cnt, d[MAXN][2], f[MAXN][2], n;

map<string, int> id;

int ID(string s)

{

	if(!id.count(s)) id[s] = cnt++;

	return id[s];

}

int dp(int u, int k)

{

	f[u][k] = 1; d[u][k] = k;

	REP(i, 0, son[u].size())

	{

		int v = son[u][i];

		if(k == 1)

		{

			d[u][k] += dp(v, 0);

			if(!f[v][0]) f[u][k] = 0;

		}

		else

		{

			d[u][k] += max(dp(v, 1), dp(v, 0));

			if(d[v][1] == d[v][0]) f[u][k] = 0;

			if(d[v][1] > d[v][0] && !f[v][1]) f[u][k] = 0;

			if(d[v][1] < d[v][0] && !f[v][0]) f[u][k] = 0;

		}

	}

	return d[u][k];

}

int main()

{

	string s, s2;

	while(cin >> n >> s)

	{

		cnt = 0;

		id.clear();

		REP(i, 0, n) son[i].clear();	

		ID(s);

		REP(i, 0, n - 1)

		{

			cin >> s >> s2;

			son[ID(s2)].push_back(ID(s));

		}

		printf("%d ", max(dp(0, 0), dp(0, 1)));

		bool ok = false;

		if(d[0][1] > d[0][0] && f[0][1]) ok = true;

		if(d[0][1] < d[0][0] && f[0][0] ) ok = true;

		printf("%s\n", ok ? "Yes" : "No");

	}

	return 0;

}

巴特西

紫书例题 9-13 UVa 1220 （最大独立子集）

最新文章

热门文章

巴特西

紫书 例题 9-13 UVa 1220 （最大独立子集）

最新文章

热门文章

紫书例题 9-13 UVa 1220 （最大独立子集）