算法：uva 10859 Placing Lampposts （树形dp）

算法：uva 10859 Placing Lampposts （树形dp）2014-01-05 csdn shuangde题目大意

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

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

思路

这是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<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<cmath>#include<cstring>using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 1010;vector<int>adj[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
", ans/M, m-（ans%M）, ans%M）;}return 0;}