UVA 1292 - Strategic game



守卫城市，城市由n个点和n-1条边组成的树，要求在点上安排士兵，守卫与点相连的边。问最少要安排多少士兵。



典型的树形dp。每一个点有两个状态:

dp[t][i]表示t节点在i状态下其所在的子树所有的边都被守卫的最少士兵数量。

有士兵守卫和没有士兵守卫。假设有士兵守卫。其子节点的状态随意。

假设没有士兵。子节点必须所有都有士兵守卫。



dp[t][0] = sum{dp[ti][1]};

dp[t][1] = sum{min(dp[t1][0], dp[ti][1])};

#include <bits/stdc++.h>

using namespace std;

int n, a, b, c;

int dp[1505][2];

vector<int> v[1505];

void DP(int t, int fa) {

	dp[t][0] = 0;

	dp[t][1] = 1;

	for (int i=0; i<v[t].size(); i++) {

		if (v[t][i] == fa) continue;

		DP(v[t][i], t);

		dp[t][0] += dp[v[t][i]][1];

		dp[t][1] += min(dp[v[t][i]][0], dp[v[t][i]][1]);

	}

}

int main () {

	for (; scanf ("%d", &n) == 1; ) {

		for (int i=0; i<=n; i++) v[i].clear();

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

			scanf ("%d:(%d)", &a, &b);

			for (int i=1; i<=b; i++) {

				scanf ("%d", &c);

				v[a].push_back(c);

				v[c].push_back(a);

			}

		}

		DP(0, -1);

		printf("%d\n", min(dp[0][0], dp[0][1]));

	}

	return 0;

}