[SCOI2005]王室聯(lián)邦?

類似樹分塊

>=B,并且<=3B

直接dfs，用一個全局棧記錄未規(guī)定省份的元素

dfs(y)上來，如果棧內(nèi)元素>=B，就彈出來變成一個省，并且省會是x（x不在該省內(nèi)）

從x回溯前把x加入棧內(nèi)

這樣，每個省的大小其實<=2*B-1（B-1+B）

最后會剩下和1相連的一些，總大小最多是B

必然有一個元素和最后一個省相鄰

直接并入最后一個省即可

?

數(shù)據(jù)中沒有無解的情況

無解的話也就是n<B？

n=B的情況其實要特判的。但是數(shù)據(jù)水233333

?

復(fù)雜度O(n)

?代碼：

#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){char ch;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=1005;
int n,B;
struct node{int nxt,to;
}e[2*N];
int hd[N],cnt;
void add(int x,int y){e[++cnt].nxt=hd[x];e[cnt].to=y;hd[x]=cnt;
}
int sta[N],top;
int be[N],rt[N];
int tot;
void dfs(int x,int fa){int now=top;for(reg i=hd[x];i;i=e[i].nxt){int y=e[i].to;if(y==fa) continue;dfs(y,x);if(top-now>=B){rt[++tot]=x;while(top!=now) be[sta[top--]]=tot;}}sta[++top]=x;
}
int main(){rd(n);rd(B);int x,y;for(reg i=1;i<n;++i){rd(x);rd(y);add(x,y);add(y,x);}dfs(1,0);while(top) be[sta[top--]]=tot;printf("%d\n",tot);for(reg i=1;i<=n;++i){printf("%d ",be[i]);}puts("");for(reg i=1;i<=tot;++i){printf("%d ",rt[i]);}return 0;
}}
signed main(){Miracle::main();return 0;
}/*Author: *Miracle*Date: 2019/2/1 10:42:10
*/

?

轉(zhuǎn)載于:https://www.cnblogs.com/Miracevin/p/10345094.html

總結(jié)

以上是生活随笔為你收集整理的[SCOI2005]王室联邦的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。