给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。
在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该尽量大。
这题教会了我一个很有用的技巧：有两个所求的值要优化，比如让a尽量小，ｂ也尽量小
那么可以转化为让 M*a+b尽量小，其中Ｍ应该是一个比“a的最大值和b的最小值之差”还要大的数
最终的答案为ans/M, ans%M
回到这题，要求放的灯总数最小，被两盏灯同时照亮的边数尽量大。
因为每条边要么被一盏灯照亮，要么被两盏灯照亮，所以可以转换为：
求：放的灯总数量最少，被一盏灯照亮的边数尽量少。
就可以变成球 M*a+b 的最小值，ａ为放置的灯数量，ｂ为被一盏灯照的边数
dp[u][1]表示u点放灯时的整个子树最小值
dp[u][0]表示u点不放灯时的整个子树最小值
如果u放，那么u个子结点可以选择放，也可以不放，选择其中较小的值。如果选的是不照，就要增加一条只有一个灯照的边
如果u不放，那么其子结点就必须选择要放，而且每条边都只有一个灯照
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
using namespace std;
vector<int> e[1010];
int tt,n,m;
bool vis[1010];
int dp[1010][2];
void dfs(int u)
{
vis[u]=1;
dp[u][0]=0;
dp[u][1]=2000;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(vis[v])
continue;
dfs(v);
dp[u][0]+=dp[v][1]+1;
if(dp[v][1]>dp[v][0])
dp[u][1]+=dp[v][0]+1;
else
dp[u][1]+=dp[v][1];
}
}
int main()
{
scanf("%d",&tt);
while(tt--)
{
int ans=0;
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
e[i].clear();
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{
dfs(i);
ans+=min(dp[i][0],dp[i][1]);
}
}
printf("%d %d %d\n",ans/2000,m-(ans%2000),ans%2000);
}
return 0;
}
原文：http://www.cnblogs.com/water-full/p/4532702.html