首页 > 其他 > 详细

「SCOI2005」王室联邦

时间:2020-01-23 23:00:35      阅读:101      评论:0      收藏:0      [点我收藏+]

「SCOI2005」王室联邦

传送门
树分块。
考虑把树,按照节点个数每 \(B\) 个分块,把块顶作为省会。
这是具体证明
参考代码:

#include <cstdio>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template < class T > inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
    s = f ? -s : s;
}

const int _ = 1010;

int tot, head[_], nxt[_ << 1], ver[_ << 1];
inline void Add_edge(int u, int v)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

int n, B, cnt, num, rt[_], bel[_], x[_];

inline void dfs(int u, int f) {
    int tmp = num;
    for (rg int i = head[u]; i; i = nxt[i]) {
        int v = ver[i]; if (v == f) continue;
        dfs(v, u);
        if (num - tmp >= B) {
            rt[++cnt] = u;
            while (num > tmp) bel[x[num--]] = cnt;
        }
    }
    x[++num] = u;
}

int main() {
#ifndef ONLINE_JUDGE
    file("cpp");
#endif
    read(n), read(B);
    for (rg int u, v, i = 1; i < n; ++i)
        read(u), read(v), Add_edge(u, v), Add_edge(v, u);
    dfs(1, 0);
    if (!cnt) rt[++cnt] = 1;
    while (num) bel[x[num--]] = cnt;
    printf("%d\n", cnt);
    for (rg int i = 1; i <= n; ++i) printf("%d%c", bel[i], " \n"[i == n]);
    for (rg int i = 1; i <= cnt; ++i) printf("%d%c", rt[i], " \n"[i == n]);
    return 0;
}

「SCOI2005」王室联邦

原文:https://www.cnblogs.com/zsbzsb/p/12231578.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!