「SCOI 2005」王室联邦

发表于 | | 阅读次数:
字数统计: 757 字

Description

题目链接：BZOJ 1086

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有 $n$ 个城市，编号为 $1\dots n$。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。

为了防止管理太过分散，每个省至少要有 $B$ 个城市，为了能有效的管理，每个省最多只有 $3B​$ 个城市。

每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。

一个城市可以作为多个省的省会。

数据范围：$1\le n\le 3000​$

Solution

我们可以考虑这样一个构造方法：

  1. 我们 $\text{DFS}$ 整棵树，处理每个节点时，将其一部分子节点分块，将未被分块的子节点返回到上一层。
  2. 枚举 $u$ 的每个子节点 $v$，递归处理子树后，将每个子节点返回的未被分块的节点添加到集合 $S$ 中，一旦 $\vert S\vert\ge B$ 就把 $S$ 作为一个新的块并将 $u$ 作为省会，然后清空 $S$ 并继续枚举 $v$。
  3. 处理完所有子树后，将 $u$ 也加入到集合 $S$ 中，此时在 $S$ 中的节点为未被分块的节点，将被返回到上一层，显然 $S$ 的大小最大为 $B-1$ 个子树节点 + $u$ 节点本身，即 $\vert S\vert\le B$。
  4. 由于返回的集合的大小最大为 $B$，对于一个子树会对集合最多增加 $B-1$ 个节点，那么每个块的大小最大为 $2B-1$，满足条件。
  5. 在 $\text{DFS}$ 结束后，集合 $S$ 中可能还有节点（最多有 $B$ 个），那么我们把这 $B$ 个节点并入最后一个块（以根节点为省会的最后一个块）中，那么这个块的大小最大为 $3B-1$，符合条件。

时间复杂度：$O(n)​$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <cstdio>

const int N=1e3+5,M=2e3+5;
int n,B,sz,cnt,tot,lnk[N],ter[M],nxt[M],st[N],rt[N],bel[N];

void add(int u,int v) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
void dfs(int u,int p) {
    int cnr=sz;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==p) continue;
        dfs(v,u);
        if(sz-cnr>=B) {
            rt[++cnt]=u;
            while(sz>cnr) bel[st[sz--]]=cnt;
        }
    }
    st[++sz]=u;
}
int main() {
    scanf("%d%d",&n,&B);
    for(int i=1;i<n;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    if(!cnt) rt[++cnt]=1;
    while(sz) bel[st[sz--]]=cnt;
    printf("%d\n",cnt);
    for(int i=1;i<=n;++i) printf("%d%c",bel[i]," \n"[i==n]);
    for(int i=1;i<=cnt;++i) printf("%d%c",rt[i]," \n"[i==cnt]);
    return 0;
}
0%