首页 > 代码库 > 【bzoj1086】 scoi2005—王室联邦
【bzoj1086】 scoi2005—王室联邦
http://www.lydsy.com/JudgeOnline/problem.php?id=1086 (题目链接)
本来是来学树上分块的，没想到正解是贪心+dfs。。。
题意：求将树分为几个联通块，每个联通块大小大于B小于3B，是否可行。
Solution
题都没看就翻了题解。。发现时贪心+dfs。
一遍dfs即可。注意到以x为根节点时，其儿子s，则子树s中与s相连的节点的连通块，如果要构成一个省，既可以s作为省会还可以x作为省会。如果用s作为省会，那s的子树 < b怎么办？所以以x为省会。这样将x的子树中没有标号的每超过b个就连成一个省份。当然如果以x为节点的树小于b，那就在x的父节点中操作。由于是从下往上操作，所以那些没有标号的一定与x的其中一个儿子s构成连通块。那为什么是3b呢？这样不是2b就够了吗？考虑到对于根节点r，最后还剩下小于b个的节点没有省份，这样将剩下来的点并入最后一个省份，以x为省会即可。
考虑操作。显然这需要一个栈来维护，每次回去之前将x加入栈里面。然后栈中在当前树中的节点超过b个时就将这b个放到一个省里。
代码：
// bzoj3757#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>‘9‘ || ch<‘0‘) {if (ch==‘-‘) f=-1;ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int maxn=1010;struct edge {int next,to;}e[maxn<<2];int head[maxn],size[maxn],pos[maxn],q[maxn],n,B,cnt,top,c,cap[maxn];void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;}void dfs(int x,int fa) { q[++top]=x; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) { dfs(e[i].to,x); if (size[x]+size[e[i].to]>=B) { size[x]=0; cap[++cnt]=x; while (q[top]!=x) pos[q[top--]]=cnt; } else size[x]+=size[e[i].to]; } size[x]++;}void paint(int x,int fa,int c) { if (pos[x]) c=pos[x]; else pos[x]=c; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) paint(e[i].to,x,c);}int main() { scanf("%d%d",&n,&B); for (int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); insert(u,v); } if (n<B) {printf("0");return 0;} cnt=0;dfs(1,0); if (!cnt) cap[++cnt]=1; paint(1,0,cnt); printf("%d\n",cnt); for (int i=1;i<=n;i++) printf("%d ",pos[i]); printf("\n"); for (int i=1;i<=cnt;i++) printf("%d ",cap[i]); return 0;}
【bzoj1086】 scoi2005—王室联邦
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。