壊すとword│E-olv

menu icon

BZOJ1086 [SCOI2005]王室联邦

2015.01.16 09:32 Fri| 0 visits oi_2015| 2015_刷题日常| Text

Solution

典型的真·都比题。

忘记了输出 0 竟然也能过 = =

奇怪的贪心：DFS 过程中如果发现当前的 size 不小于 B，则将这些都划分成一个省。这样，DFS 过程中就可以将原图划分成许多小省份。当然，最终可能会有一部分节点剩余，随便划分到一个邻近的省份便符合题意。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 1005
#define M 2005

stack<int> s;
int n, b, tot, head[N], size[N], belong[N], captain[N];

struct data {
    int next, to;
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt].to = y;
    edge[cnt].next = head[x];
    head[x] = cnt;
}

void dfs(int x, int fa)
{
    s.push(x);
    for (int y, i = head[x]; i; i = edge[i].next)
        if ((y = edge[i].to) != fa)
        {
            dfs(y, x);
            if ((size[x] + size[y]) >= b)
            {
                size[x] = 0;
                captain[++tot] = x;
                while (s.top() != x)
                    belong[s.top()] = tot, s.pop();
            }
            else size[x] += size[y];
        }
    size[x]++;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> b;
    for (int x, y, i = 1; i < n; ++i)
        cin >> x >> y, add(x, y), add(y, x);
    dfs(1, 0);
    if (!tot) captain[++tot] = 1;
    while (!s.empty())
        belong[s.top()] = tot, s.pop();
    cout << tot << endl;
    for (int i = 1; i <= n; ++i)
        cout << belong[i] << " \n"[i==n];
    for (int i = 1; i <= tot; ++i)
        cout << captain[i] << " \n"[i == tot];
}
Newer