1086: [SCOI2005]王室聯邦 Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge Submit: 1557 Solved: 936 [Submit][Status][Discuss] Description “余”人國的國王想重新編制他的國家。他想把他的國家劃分成若干個省，每個省都由他們王室聯邦的一個成 員來管理。他的國家有n個城市，編號為1..n。一些城市之間有道路相連，任意兩個不同的城市之間有且僅有一條 直接或間接的道路。為了防止管理太過分散，每個省至少要有B個城市，為了能有效的管理，每個省最多只有3B個 城市。每個省必須有一個省會，這個省會可以位于省內，也可以在該省外。但是該省的任意一個城市到達省會所經 過的道路上的城市（除了最后一個城市，即該省省會）都必須屬于該省。一個城市可以作為多個省的省會。聰明的 你快幫幫這個國王吧！ Input 第一行包含兩個數N，B（1<=N<=1000, 1 <= B <= N）。接下來N－1行，每行描述一條邊，包含兩個數，即這 條邊連接的兩個城市的編號。 Output 如果無法滿足國王的要求，輸出0。否則輸出數K，表示你給出的劃分方案中省的個數，編號為1..K。第二行輸 出N個數，第I個數表示編號為I的城市屬于的省的編號，第三行輸出K個數，表示這K個省的省會的城市編號，如果 有多種方案，你可以輸出任意一種。 Sample Input 8 2 1 2 2 3 1 8 8 7 8 6 4 6 6 5 Sample Output 3 2 1 1 3 3 3 3 2 2 1 8
/*王室聯邦分塊.保證塊直徑,大小,個數,不保證聯通.并不會證明. */#include<cstring>#include<cstdio>#include<queue>#define MAXN 1001using namespace std;struct data{int v,next;}e[MAXN*2];int n,m,k,top,tot,cut,stack[MAXN],root[MAXN],fa[MAXN],head[MAXN],belong[MAXN];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void add(int u,int v){ e[++cut].v=v; e[cut].next=head[u]; head[u]=cut;}void dfs(int u,int f){ fa[u]=f; int sum=top; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(v==f) continue; fa[v]=u,dfs(v,u); if(top-sum>=k) { root[++tot]=u; do { belong[stack[top]]=tot,top--; }while(top!=sum); } } stack[++top]=u; return ;}int main(){ int x,y; n=read(),k=read(); for(int i=1;i<=n-1;i++) x=read(),y=read(),add(x,y),add(y,x); dfs(1,1); while(top) { x=stack[top--]; belong[x]=tot; }新聞熱點
疑難解答
