UVa 10859 Placing Lampposts / 树形DP

给你一个图 在尽量少的节点上放灯 使得所有边所有边都被照亮 每盏灯照亮以他为端点的所有边

求在灯总数最小的前提下 被两盏灯照亮的边数尽量大（即被一条边照亮的边数尽量小）

另x = Ma + c (a是灯的数量，c是被两盏灯照亮边数）转换求x 最小

M是一个很大的数 x取最小时 x/m整数部分就是所求灯最小值 x%m就是被一条边照亮的边数

M比 c的最大理论值和a的最小理论值差 还要大的数 那么x都是a起到决定性作用 a相同时在取决于c

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 1010;
vector <int> adj[maxn];
int vis[maxn][2], dp[maxn][2], n, m;

int dfs(int i, int j, int f)
{
	if(vis[i][j])
		return dp[i][j];
	vis[i][j] = 1;
	int& ans = dp[i][j];
	ans = 2000;
	for(int k = 0; k < adj[i].size(); k++)
		if(adj[i][k] != f)
			ans += dfs(adj[i][k], 1, i);
	if(!j && f >= 0)//不是根并且父节点没有放灯 那么被一盏灯照亮的边加1 
		ans++;
	if(j || f < 0)//是根 或者 父节点已经放了灯才能不放
	{
		int sum = 0;
		for(int k = 0; k < adj[i].size(); k++)
			if(adj[i][k] != f)
				sum += dfs(adj[i][k], 0 , i);
		if(f >= 0)//不放的话父节点肯定已经放了 那么被一盏灯照亮的边加1 
			sum++;
		ans = min(ans, sum);
	}
	return ans;
}
int main()
{
	int T, u, v;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d", &n, &m);
		for(int i = 0; i < n; i++)
			adj[i].clear();
		for(int i = 0; i < m; i++)
		{
			scanf("%d %d", &u, &v);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		memset(vis, 0 ,sizeof(vis));
		int ans = 0;
		for(int i = 0; i < n; i++)
			if(!vis[i][0])
				ans += dfs(i, 0, -1);
		printf("%d %d %d\n", ans/2000, m-ans%2000, ans%2000);
	}
	return 0;
}

UVa 10859 Placing Lampposts / 树形DP

原文：http://blog.csdn.net/u011686226/article/details/18449841