首页 > 代码库 > 【BZOJ】【1086】 【SCOI2005】王室联邦
【BZOJ】【1086】 【SCOI2005】王室联邦
树分块
orz vfk && PoPoQQQ
http://vfleaking.blog.163.com/blog/static/174807634201231684436977/ http://blog.csdn.net/popoqqq/article/details/42772237这题是要把树分成一块一块的……（感觉好像不是原来理解的树分块处理操作啊……）
每块大小B<= size <=3B ，一种简单粗暴的想法就是dfs，每找到B个就分一块，但是这样连通性不能保证（一颗子树的下半截和另一棵子树的上半截组成一块）。所以我们就想：能不能从底部往上组块，每棵子树较深的部分自己成块，然后靠近根的部分组成一个大块
这样就可以保证连通性和块大小不会超了，最后dfs结束后肯定还会有剩余的未组成块的节点，把它们归到最后一个块就可以了。证明看vfk博客就行……
至于实现这个“等待序列”，用的是PoPoQQQ的方法：用栈来实现，对当前节点x，它的等待序列就是bottom--top（bottom初始化为top，然后再向栈里加的元素就是他的儿子）……呃……这个自己手画一个简单的就能理解了吧……？或者脑补一下……嗯
1 /************************************************************** 2 Problem: 1086 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:12 ms 7 Memory:1320 kb 8 ****************************************************************/ 9 10 //BZOJ 108611 #include<cstdio>12 #include<cstring>13 #include<cstdlib>14 #include<iostream>15 #include<algorithm>16 #define rep(i,n) for(int i=0;i<n;++i)17 #define F(i,j,n) for(int i=j;i<=n;++i)18 #define D(i,j,n) for(int i=j;i>=n;--i)19 using namespace std;20 void read(int &v){21 v=0; int sign=1; char ch=getchar();22 while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();}23 while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();}24 v*=sign;25 }26 /******************tamplate*********************/27 const int N=2015;28 int head[N],to[N],next[N],cnt;29 void add(int x,int y){30 to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;31 to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt;32 }33 /********************edge***********************/34 int n,B,K;35 int st[N],top;36 int belong[N],root[N],tot;37 void dfs(int x,int fa){38 int bottom=top;39 for(int i=head[x];i;i=next[i])40 if (to[i]!=fa){41 dfs(to[i],x);42 if (top-bottom>=B){43 root[++tot]=x;44 while(top!=bottom)45 belong[st[top--]]=tot;46 }47 }48 st[++top]=x;49 }50 51 int main(){52 read(n); read(B);53 int x,y;54 F(i,2,n){55 read(x); read(y);56 add(x,y);57 }58 dfs(1,0);59 while(top) belong[st[top--]]=tot;60 printf("%d\n",tot);61 F(i,1,n) printf("%d ",belong[i]);62 printf("\n");63 F(i,1,tot) printf("%d ",root[i]);64 return 0;65 }
【BZOJ】【1086】 【SCOI2005】王室联邦
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。