题目： 点击打开链接

题目大意
给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。

在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该尽量大。

思路
这是LRJ《入门经典》上的例题。

这题教会了我一个很有用的技巧：有两个所求的值要优化，比如让a尽量小，ｂ也尽量小

那么可以转化为让 M*a+b尽量小，其中Ｍ应该是一个比“a的最大值和b的最小值之差”还要大的数

最终的答案为ans/M, ans%M

回到这题，要求放的灯总数最小，被两盏灯同时照亮的边数尽量大。

因为每条边要么被一盏灯照亮，要么被两盏灯照亮，所以可以转换为：

求：放的灯总数量最少，被一盏灯照亮的边数尽量少。

就可以变成球 M*a+b 的最小值，ａ为放置的灯数量，ｂ为被一盏灯照的边数

f[u][1]表示u点放灯时的整个子树最小值
f[u][0]表示u点不放灯时的整个子树最小值

如果u放，那么u个子结点可以选择放，也可以不放，选择其中较小的值。如果选的是不照，就要增加一条只有一个灯照的边

如果u不放，那么其子结点就必须选择要放，而且每条边都只有一个灯照

下面的我的代码和书上实现的不一样，更简洁

代码
 /**========================================== *  
 This is a solution for ACM/ICPC problem * *  
 @source：uva-10859 Placing Lampposts *   
@type:  树形dp *   @author: shuangde *  
 @blog: blog.csdn.net/shuangde800 *  
 @email: zengshuangde@gmail.com *===========================================*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;const int MAXN = 1010;
vectoradj[MAXN];
bool vis[MAXN];
int n, m;int f[MAXN][2];
const int M = 2000;void dfs(int u) {    vis[u] = true;  
  f[u][0] = 0; 
   f[u][1] = M;  
  for(int i = 0;
 i < adj[u].size(); ++i) {        int v = adj[u][i]; 
        if(vis[v]) continue;        dfs(v);  
      f[u][0] += f[v][1] + 1;  
      if (f[v][0] < f[v][1]) {            f[u][1] += f[v][0] + 1;  
      } else {            f[u][1] += f[v][1];      
  }     }}int main(){    int nCase;   
 scanf("%d", &nCase);   
 while(nCase--) {        scanf("%d%d", &n, &m);  
      for(int i = 0;
 i < n; ++i)             adj[i].clear();  
      for(int i = 0;
 i < m; ++i) {            int u, v;  
          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]){            dfs(i);  
          ans += min(f[i][0], f[i][1]);    
    }        printf("%d %d %d\n", ans/M, m-(ans%M), ans%M);  
  }    return 0;}