BZOJ1086 [SCOI2005]王室联邦【dfs + 贪心】

题目

　　“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成

员来管理。他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条

直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个

城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经

过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。聪明的

你快帮帮这个国王吧！

输入格式

　　第一行包含两个数N，B（1<=N<=1000, 1 <= B <= N）。接下来N－1行，每行描述一条边，包含两个数，即这

条边连接的两个城市的编号。

输出格式

　　如果无法满足国王的要求，输出0。否则输出数K，表示你给出的划分方案中省的个数，编号为1..K。第二行输

出N个数，第I个数表示编号为I的城市属于的省的编号，第三行输出K个数，表示这K个省的省会的城市编号，如果

有多种方案，你可以输出任意一种。

输入样例

8 2

1 2

2 3

1 8

8 7

8 6

4 6

6 5

输出样例

2 1 1 3 3 3 3 2

2 1 8

题解

一道长得很像难题的水题。。。【n <= 1000，无解，3B，都是什么奇奇怪怪的东西】

我们只要深搜维护一个栈，当子树剩余没有分配的城市大小>=B时，就将它们划分，首都设为当前节点，如果不足，留在栈内与下一个子树合并。若没有子树了，加上当前节点留着往上回溯和上边的节点合并。到最后还剩不到B个，就和上一次划分的城市合并

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)

using namespace std;

const int maxn = 1005,maxm = 2005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int N,B,h[maxn],ne = 0;

struct EDGE{int to,nxt;}ed[maxm];

inline void build(int u,int v){

    ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;

    ed[ne] = (EDGE){u,h[v]}; h[v] = ne++;

}

int st[maxn],fa[maxn],top = 0,cnt = 0,id[maxn],cap[maxn];

void dfs(int u){

    int to,last = top;

    Redge(u) if ((to = ed[k].to) != fa[u]){

        fa[to] = u;

        dfs(to);

        if (top - last >= B){

            cap[++cnt] = u;

            while (top > last) id[st[top--]] = cnt;

        }

    }

    st[++top] = u;

}

int main(){

    memset(h,-1,sizeof(h));

    N = RD(); B = RD();

    REP(i,N - 1) build(RD(),RD());

    dfs(1);

    while (top) id[st[top--]] = cnt;

    printf("%d\n%d",cnt,id[1]);

    for (int i = 2; i <= N; i++) printf(" %d",id[i]); printf("\n%d",cap[1]);

    for (int i = 2; i <= cnt; i++) printf(" %d",cap[i]);

    return 0;;

}

王室联邦