2018.09.16 bzoj1086: [SCOI2005]王室联邦(贪心)
2024-10-15 07:26:58
传送门
就是给树分块。
对于一个节点。
如果它的几棵子树加起来超过了下限,就把它们分成一块。
这样每次可能会剩下几个节点。
把它们都加入栈中最顶上那一块就行了。
代码:
#include<bits/stdc++.h>
#define N 1005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int first[N],cnt=0,n,b,tot=0,stk[N],top=0,ans[N],belong[N];
struct edge{int v,next;}e[N<<1];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void dfs(int p,int fa){
int tmp=top;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
dfs(v,p);
if(top-tmp>=b){
ans[++tot]=p;
while(top!=tmp)belong[stk[top--]]=tot;
}
}
stk[++top]=p;
}
int main(){
n=read(),b=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
dfs(1,1);
while(top)belong[stk[top--]]=tot;
printf("%d\n",tot);
for(int i=1;i<=n;++i)printf("%d%c",belong[i],i==n?'\n':' ');
for(int i=1;i<=tot;++i)printf("%d ",ans[i]);
return 0;
}
最新文章
- Web开发技术发展历史
- Linux 学习手记(4):Linux系统常用Shell命令
- swift为UIView添加extension扩展frame
- Android Handler leak 分析及解决办法
- 做一个自己的最小Linux系统
- 利用jpedal进行pdf转换成jpeg,jpg,png,tiff,tif等格式的图片
- SRM 390(1-250pt)
- 这些年,我收集的JavaScript代码(一)
- ORA-12012: error on auto execute of job &;quot;ORACLE_OCM
- 用手机或外部设备在同一局域网下访问虚拟主机wampsever的方法版本号是2.4.9
- java集合系列——List集合之Vector介绍(四)
- Liunx vi编辑器一些指令
- 通过反射实现Microsoft Visual Studio International Pack 1.0 SR1里面的两个类
- Nginx之(二)Nginx安装
- Snackbar 提醒
- HackerRank-Python攻城歷程-2.List comprehensions
- Go语言学习之11 日志收集系统kafka库实战
- linux——文件操作
- 小tips:JS语法之标签(label)
- RandomStringUtils