首页 > 代码库 > poj 3107 Godfather
poj 3107 Godfather
http://poj.org/problem?id=3107
树形dp
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 55000 5 using namespace std; 6 const int inf=1<<30; 7 8 int head[maxn],e,n; 9 int dp[maxn];10 bool vis[maxn];11 int minn;12 int cnt;13 int ans[maxn];14 struct node15 {16 int u,v;17 int next;18 }p[maxn*2];19 20 void add(int u,int v)21 {22 p[e].u=u;23 p[e].v=v;24 p[e].next=head[u];25 head[u]=e++;26 }27 28 void cls()29 {30 e=0;31 cnt=0;32 memset(ans,0,sizeof(ans));33 minn=inf;34 memset(head,-1,sizeof(head));35 }36 37 void dfs(int u)38 {39 int min1=-1;40 if(vis[u]) return ;41 vis[u]=true;42 dp[u]=1;43 for(int i=head[u]; i!=-1; i=p[i].next)44 {45 int v=p[i].v;46 if(vis[v]) continue;47 dfs(v);48 dp[u]+=dp[v];49 min1=max(min1,dp[v]);50 }51 min1=max(min1,n-dp[u]);52 if(min1<minn)53 {54 cnt=0;55 ans[cnt++]=u;56 minn=min1;57 }58 else if(min1==minn)59 {60 ans[cnt++]=u;61 }62 }63 64 int main()65 {66 while(scanf("%d",&n)!=EOF)67 {68 cls();69 for(int i=1; i<=n-1; i++)70 {71 int u,v;72 scanf("%d%d",&u,&v);73 add(u,v);74 add(v,u);75 }76 dfs(1);77 sort(ans,ans+cnt);78 for(int i=0; i<cnt; i++)79 {80 if(i==0) printf("%d",ans[i]);81 else printf(" %d",ans[i]);82 }83 printf("\n");84 }85 return 0;86 }
poj 3107 Godfather
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。