uva 10859 Placing Lampposts / Tree DP

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1800

　　树DP，要求求出最小覆盖点集，并且要求两端都有覆盖的边尽可能多。于是，这题可以通过赋权，求树的最小权值。无向无环图通过dfs变成有根树一棵，然后对每个树根DP，最后得到答案。

代码如下：

View Code

 1 #define REP(i, n) for (int i = 0; i < (n); i++)
 2 
 3 int dp[2][N];
 4 bool vis[N];
 5 VI rel[N];
 6 
 7 void input(int n, int m) {
 8     REP(i, n) {
 9         rel[i].clear();
10         vis[i] = false;
11     }
12     int u, v;
13     REP(i, m) {
14         cin >> u >> v;
15         rel[u].PB(v);
16         rel[v].PB(u);
17     }
18 }
19 
20 void dfs(int x) {
21     vis[x] = true;
22     dp[0][x] = 0;
23     dp[1][x] = 1 << 12;
24     REP(i, SZ(rel[x])) {
25         int t = rel[x][i];
26         if (!vis[t]) {
27             dfs(t);
28             dp[0][x] += dp[1][t] + 1;
29             if (dp[0][t] < dp[1][t]) dp[1][x] += dp[0][t] + 1;
30             else dp[1][x] += dp[1][t];
31         }
32     }
33 //    cout << x << " :";
34 //    REP(i, SZ(rel[x])) cout << rel[x][i] << ends;
35 //    cout << endl;
36 //    cout << x << ends << dp[0][x] << ends << dp[1][x] << endl;
37 }
38 
39 int work(int n) {
40     _clr(vis);
41     int ret = 0;
42     REP(i, n) {
43         if (!vis[i]) {
44             dfs(i);
45             ret += min(dp[0][i], dp[1][i]);
46         }
47     }
48     return ret;
49 }
50 
51 int main() {
52 //    freopen("in", "r", stdin);
53     int T, n, m;
54     while (cin >> T) {
55         while (T--) {
56             cin >> n >> m;
57             input(n, m);
58             int ans = work(n);
59             cout << (ans >> 12) << ' ' << m - (ans & 0x00000FFF) << ' ' << (ans & 0x00000FFF) << endl;
60         }
61     }
62     return 0;
63 }

——written by Lyon