首页 > 代码库 > sgu-216 Royal Federation
sgu-216 Royal Federation
题目大意:
给定n,B,然后给你一个n个节点的树,要求你将其分成几块(k),要求每一块的点数大于等于B并且小于等于3B,然后个每一块设定一个capital(capital可以不再这个块中,但是块中的点到capital的路径上不能有不属于这个块的点),要你输出k,然后每个节点属于的块的编号,接着输出每个块的capital。
解题思路:
一道不是很难构造题,DFS一遍,然后如果有一个节点的一些儿子节点大于B,就直接分为一个块,capital为这个节点,剩下的没有包含的点就计入最后一个,然后判断一下就行了,详细看代码吧,感觉不是很难懂。
AC代码;
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <iostream> #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)>(b)?(b):(a)) using namespace std; struct bian_ { int num; int next; }bian[20020]={{0,0}}; int belong[10010]={0}; int First[10010]={0}; int n,B; int capitals[10010]={0}; int GG=0; int s[10010]={0}; int dui[100010]={0}; int duip=0; int ss[10010]={0}; void Add(int p,int q,int k) { bian[k].num=q; bian[k].next=First[p]; First[p]=k; return; } void DFS(int k,int fa) { int tmp=0; dui[++duip]=k; for(int p=First[k];p!=0;p=bian[p].next) { if(bian[p].num==fa) continue; DFS(bian[p].num,k); tmp+=s[bian[p].num]; if(tmp<B) continue; GG++; capitals[GG]=k; for(;duip>0 && dui[duip]!=k;) { belong[dui[duip]]=GG; dui[duip--]=0; } tmp=0; } s[k]=1+tmp; return; } int main() { scanf("%d%d",&n,&B); for(int i=1;i<n;i++) { int p,q; scanf("%d%d",&p,&q); Add(p,q,(i<<1)-1); Add(q,p,i<<1); } if(n<B) cout<<0<<endl; else if(n<=3*B) { cout<<1<<endl; for(int i=1;i<=n;i++) printf("1%c",i==n?'\n':' '); cout<<1<<endl; } else { DFS(1,-1); for(int i=1;i<=n;i++) { if(belong[i]==0) belong[i]=GG; ss[belong[i]]++; } for(int i=1;i<=GG;i++) if(ss[i]<B || ss[i]>3*B) { cout<<0<<endl; goto END; } cout<<GG<<endl; for(int i=1;i<=n;i++) printf("%d%c",belong[i],i==n?'\n':' '); for(int i=1;i<=GG;i++) printf("%d%c",capitals[i],i==GG?'\n':' '); END:; } return 0; }
sgu-216 Royal Federation
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。