首页 > 代码库 > POJ 3107 Godfather （树形dp）
POJ 3107 Godfather （树形dp）
题目链接
虽然题目不难，但是1A还是很爽， 只是刚开始理解错题意了，想了好久。 还有据说这个题用vector会超时，看了以后还是用邻接吧。
题意：
给一颗树，保证是一颗树，求去掉一个点以后的联通块里节点的数目的 最大值最小，求这样的点，并按照递增顺序输出。
分析：
d[father] = max(n-sum, d[son]); sum代表这个节点以下的全部节点总数， 去掉一个节点的联通块的最大的节点数 等于 整个树里的节点数减去这个节点下的总数 和 子树的数目的
最大值。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <vector> 8 #define LL __int64 9 const int maxn = 50000+10;10 const int INF = 1<<28;11 using namespace std;12 int head[maxn], vis[maxn], t, d[maxn];13 int mi, n;14 struct node15 {16 int u, v, ne;17 }e[2*maxn];18 19 void add(int u, int v)20 {21 e[t].u = u;22 e[t].v = v;23 e[t].ne = head[u];24 head[u] = t++;25 }26 int dfs(int son, int fa)27 {28 int i, tmp, sum = 1, x; //sum是以son为根节点的子树的全部的节点数29 for(i = head[son]; i != -1; i = e[i].ne)30 {31 tmp = e[i].v;32 if(tmp == fa) continue; //避免回去。33 x = dfs(tmp, son);34 sum += x;35 d[son] = max(d[son], x);36 }37 d[son] = max(d[son], n-sum);38 if(d[son]<mi)39 mi = d[son];40 return sum;41 }42 int main()43 {44 int i, f;45 while(~scanf("%d", &n))46 {47 memset(e, 0, sizeof(e));48 memset(head, -1, sizeof(head));49 memset(vis, 0, sizeof(vis));50 memset(d, 0, sizeof(d));51 t = 0;52 mi = INF;53 54 for(i = 1; i < n; i++)55 {56 int u, v;57 scanf("%d%d", &u, &v);58 add(u, v);59 add(v, u);60 }61 dfs(1, -1); //把给的树看成以1为根节点。62 63 f = 0;64 for(i = 1; i <= n; i++)65 {66 if(d[i]==mi)67 {68 if(f)69 printf(" %d", i);70 else71 printf("%d", i);72 f = 1;73 }74 }75 printf("\n");76 }77 return 0;78 }
POJ 3107 Godfather （树形dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。