BZOJ1086 [SCOI2005]王室联邦
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]; }