uva 10859 - Placing Lampposts(树形dp）

题目链接:uva 10859 - Placing Lampposts

题目大意：给定一个无向无环图，要求在点上放灯，如果某一点上放了等，则可以照亮与它相通的边，现在要求放尽量少得等，使得所有边都被照亮，并且输出灯数，被照亮两次的边数（即边的两个端点均放置灯），被照亮一次的边。 如果等数一样的话，按照被照亮一次边越大的方案。

解题思路：树形dp，每次枚举某个顶点作为根，对于每个点有放与不放两种可能，均进行考虑；然后每放一盏灯+2000（因为边的最大数量为1000），每增加1条照亮一次的边+1.

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1010;
const int M = 2000;

int n, m, v[N], dp[N][2];
vector<int> g[N];

void init() {
	int a, b;
	scanf("%d%d", &n, &m);

	for (int i = 0; i < n; i++) g[i].clear();
	memset(v, 0, sizeof(v));
	memset(dp, 0, sizeof(dp));

	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
}

void dfs(int x) {
	v[x] = 1;
	dp[x][0] = 0;
	dp[x][1] = M;

	for (int i = 0; i < g[x].size(); i++) {
		int u = g[x][i];
		if (v[u]) continue;
		dfs(u);
		dp[x][0] += dp[u][1] + 1;
		if (dp[u][1] > dp[u][0]) {
			dp[x][1] += dp[u][0] + 1;
		} else {
			dp[x][1] += dp[u][1];
		}
	}
}

void solve () {
	int ans = 0;
	for (int i = 0; i < n; i++) if (!v[i]) {
		dfs(i);
		ans += min(dp[i][0], dp[i][1]);
	}
	printf("%d %d %d\n", ans/M, m - (ans%M), ans%M);
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		solve();
	}
	return 0;
}