树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