首页 > 代码库 > POJ - 3659 Cell Phone Network（树形dp---树的最小点支配集）
POJ - 3659 Cell Phone Network（树形dp---树的最小点支配集）
题意：有N个点，N-1条边，任意两点可达，由此形成了一棵树。选取一个点a，它可覆盖自己以及与自己相邻的点，选取尽量少的点a，使得树中所有点都被覆盖，即求树的最小点支配集。
分析：
1、对于每一个点cur，要想使其被覆盖，有三种情况：
dp[cur][0]---在该点建立塔
dp[cur][1]---在该点的子结点建立塔
dp[cur][2]---在该点的父结点建立塔
2、对于点cur的子结点x，要使其被覆盖：
(1)dp[cur][0] += Min(Min(dp[x][0], dp[x][1]), dp[x][2]);
在cur处建塔的情况下，x可建塔，x的子节点可建塔，x的父结点即cur建塔，三者取最小值，并累加。
(2)dp[cur][2] += Min(dp[x][0], dp[x][1]);
在cur的父结点建塔的情况下，x可建塔，x的子结点可建塔，两者取最小值，并累加。
(3)dp[cur][1] += Min(dp[x][0], dp[x][1]);
在cur的子结点建塔的情况下，至少需要cur的一个子结点建塔cur才能被覆盖，所以对于每一个子结点x，x可建塔，x的子结点可建塔，两者取最小值
与此同时，记录在取最小值的情况下，cur是否有能建塔的子结点，若没有，需要将cur的一个子结点变成可建塔，选取abs(dp[x][1] - dp[x][0])最小的子结点x改变即可。
3、dp[cur][0]最后要加1，因为在cur点要建塔。
#pragma comment(linker, "/STACK:102400000, 102400000")#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<sstream>#include<iterator>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<stack>#include<deque>#include<queue>#include<list>#define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 10000 + 10;const int MAXT = 10000 + 10;using namespace std;int N;vector<int> v[MAXN];int dp[MAXN][5];void dfs(int cur, int father){ memset(dp[cur], 0, sizeof dp[cur]); int len = v[cur].size(); int dif = INT_INF; bool ok = false; for(int i = 0; i < len; ++i){ int x = v[cur][i]; if(x == father) continue; if(dp[x][0] == INT_INF) dfs(x, cur); dp[cur][0] += Min(Min(dp[x][0], dp[x][1]), dp[x][2]); dp[cur][2] += Min(dp[x][0], dp[x][1]); dif = Min(dif, abs(dp[x][1] - dp[x][0])); if(dp[x][0] < dp[x][1]){ ok = true; dp[cur][1] += dp[x][0]; } else{ dp[cur][1] += dp[x][1]; } } ++dp[cur][0]; if(!ok) dp[cur][1] += dif;}int main(){ scanf("%d", &N); for(int i = 0; i < N - 1; ++i){ int a, b; scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } memset(dp, INT_INF, sizeof dp); dfs(1, -1); printf("%d\n", Min(dp[1][0], dp[1][1])); return 0;}
POJ - 3659 Cell Phone Network（树形dp---树的最小点支配集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。