和poj1655那道求树的重心基本上一样的,代码也没多大改动。
详情请见
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 100000
int N;
vector<int> node[20005];
int num[MAXN]; //num[i]为以i结点为根的树的所有结点数。
int dp[MAXN];
bool vis[MAXN]; //由于为无向图,所以用这个来标记此结点是否计算过。
int dfs(int id)
{
int n=node[id].size();
vis[id]=1;
num[id]=1;
for(int i=0;i<n;i++)
{
if(!vis[node[id][i]])
num[id]+=dfs(node[id][i]);
}
return num[id];
}
void cal(int id)
{
int n=node[id].size();
int k;
vis[id]=1;
for(int i=0;i<n;i++)
{
k=node[id][i];
if(vis[k])
{
dp[id]=max(dp[id],N-num[id]);
}
else
{
dp[id]=max(dp[id],num[k]);
cal(k);
}
}
}
int main()
{
int a,b;
while(scanf("%d",&N)!=EOF)
{
for(int i=1;i<=N;i++)
node[i].clear();
memset(dp,0,sizeof(dp));
for(int i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
node[a].push_back(b);
node[b].push_back(a);
}
memset(vis,0,sizeof(vis));
dfs(1);
memset(vis,0,sizeof(vis));
cal(1);
for(int i=1;i<=N;i++)
{
if(dp[i]<=N/2)
printf("%d\n",i);
}
}
return 0;
}
分享到:
相关推荐
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ3411-Paid Roads【class】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
2遍dp poj_3613解题报告 poj_3613解题报告
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
北大POJ2002-Squares 解题报告+AC代码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告