BZOJ 1086 - [SCOI2005]王室联邦

Published on 2016-09-09

题目地址

描述

”余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有 n(1≤n≤1000)n(1\le n\le 1000) 个城市，编号为 。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散，每个省至少要有 BB 个城市，为了能有效的管理，每个省最多只有 3B3B 个城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。

聪明的你快帮帮这个国王吧！

分析

本题是树分块的入门题，基本思想是运用递归，递归处理子树，然后处理子树多余的部分。

我们记 DFS(u)\text{DFS}(u) 为处理 uu 及其子树，将其中的点分块，对于未被分块的点（数量 <B< B），保证它们是与 uu 联通的联通块。

对于 DFS(u)\text{DFS}(u) 的过程，递归处理子树，然后接收子树返回的未被分块的点，每个子树的这些点累在一起，一旦数量大于等于 BB，马上把他们归为一个块，以 uu 为根，显然这个块的大小不会超过 2B2B。不断这样做直到递归完子树。最后可能会剩余一些点（数量 <B< B），将它们和 uu 一起返回。

执行完 DFS(root)\text{DFS}(\mathrm{root}) 以后，还会剩余一些点，这些点数量不够 BB，但是一定与最后一个块联通，我们就让它们归到最后一个块里面去，显然，这样最后一个块的大小不会超过 3B3B，满足题目中块大小 [B,3B][B, 3B] 的限制。

这个过程可以使用一个栈来维护，但是请注意，栈只是用来帮助我们维护这个过程的，并不是说栈里的所有点都可用，当刚刚开始 DFS(u)\text{DFS}(u) 的时候，虽然栈里可能有元素，但是对于 uu 这个点来说，子树中未被分类的点还一个都没有，所以我们不能动栈里的这些元素。

有些人上来就说用栈，然后发现有问题了才修改说不让用栈底的元素，我觉得这些人是没有理解这个算法的实质，理解了算法在干什么，自然不会犯这样的错。
你或许会喷我，说我讲的不清楚，栈到底怎么用，我只能说一句：“无可奉告！”

代码

//  Created by Sengxian on 09/09/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1086 树分块
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000 + 3;
vector<int> G[MAX_N];
int n, B, stk[MAX_N], sz = 0;
int block_cnt = 0, province[MAX_N], bel[MAX_N];

void dfs(int u, int fa = -1) {
    int bottom = sz;
    for (int i = 0; i < (int)G[u].size(); ++i) {
        int v = G[u][i];
        if (v == fa) continue;
        dfs(v, u);
        if (sz - bottom >= B) {
            while (sz != bottom) {
                bel[stk[--sz]] = block_cnt;
            }
            province[block_cnt++] = u;
        }
    }
    stk[sz++] = u;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), B = ReadInt();
    for (int i = 0, f, t; i < n - 1; ++i) {
        f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t), G[t].push_back(f);
    }
    dfs(0);
    while (sz) bel[stk[--sz]] = block_cnt - 1;
    printf("%d\n", block_cnt);
    for (int i = 0; i < n; ++i)
        printf("%d%c", bel[i] + 1, i + 1 == n ? '\n' : ' ');
    for (int i = 0; i < block_cnt; ++i)
        printf("%d%c", province[i] + 1, i + 1 == block_cnt ? '\n' : ' ');
    return 0;
}
BZOJ 1104 - [POI2007]洪水pow