好贷网好贷款

uva 10859 - Placing Lampposts(树形dp)

发布时间:2016-12-3 3:58:19 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"uva 10859 - Placing Lampposts(树形dp)",主要涉及到uva 10859 - Placing Lampposts(树形dp)方面的内容,对于uva 10859 - Placing Lampposts(树形dp)感兴趣的同学可以参考一下。

题目链接:uva 10859 - Placing Lampposts 题目大意:给定一个无向无环图,要求在点上放灯,如果某一点上放了等,则可以照亮与它相通的边,现在要求放尽量少得等,使得所有边都被照亮,并且输出灯数,被照亮两次的边数(即边的两个端点均放置灯),被照亮一次的边。 如果等数一样的话,按照被照亮一次边越大的方案。 解题思路:树形dp,每次枚举某个顶点作为根,对于每个点有放与不放两种可能,均进行考虑;然后每放一盏灯+2000(因为边的最大数量为1000),每增加1条照亮一次的边+1. #include <stdio.h> #include <string.h> #include <vector> #include <algorithm> using namespace std; const int N = 1010; const int M = 2000; int n, m, v[N], dp[N][2]; vector<int> g[N]; void init() { int a, b; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) g[i].clear(); memset(v, 0, sizeof(v)); memset(dp, 0, sizeof(dp)); for (int i = 0; i < m; i++) { scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); } } void dfs(int x) { v[x] = 1; dp[x][0] = 0; dp[x][1] = M; for (int i = 0; i < g[x].size(); i++) { int u = g[x][i]; if (v[u]) continue; dfs(u); dp[x][0] += dp[u][1] + 1; if (dp[u][1] > dp[u][0]) { dp[x][1] += dp[u][0] + 1; } else { dp[x][1] += dp[u][1]; } } } void solve () { int ans = 0; for (int i = 0; i < n; i++) if (!v[i]) { dfs(i); ans += min(dp[i][0], dp[i][1]); } printf("%d %d %d\n", ans/M, m - (ans%M), ans%M); } int main () { int cas; scanf("%d", &cas); while (cas--) { init(); solve(); } return 0; }

上一篇:C++中的const
下一篇:【bellman_ford】poj2240

相关文章

相关评论