Skip to content

14298: 【原4298】分割海岛

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4298

问题描述

在一片海域里面有N个海岛连成了树的形状,即互相连通。现在我们想去掉一个海岛U把整片连通区域分割成更小的连通区域,并且希望满足每个小连通区域的海岛数量不超过$k$,请根据输入的海岛区域信息来输出所有可能使分割愿望成立的海岛U的编号(保证给出的海岛信息可以构成一棵树)。

输入格式

第1行,两个整数n和k,代表有n个海岛,且每个海岛的编号为1,2,...,n。 第2~n行,每行两个整数a,b,代表海岛a和海岛b之间连通。

输出格式

一行

如果没有符合条件的海岛U,则输出None,

如果有,从大到小依次输出所有满足条件的海岛U的编号,用空格分开。

样例输入1

10 5
1 7
4 7
6 1
8 4
9 4
5 6
2 1
3 1
10 8

样例输出1

7 1

样例解释

去掉海岛1后,剩下的连通块中海岛数量分别为5,2,1,1,均不超过5

去掉海岛7后,剩下的连通块中海岛数量分别为4,5,均不超过5

数据范围与约束

对于百分之三十的数据,$1<k<n\le30$

对于百分之六十的数据,$1<k<n\le1000$

对于百分之百的数据,$1<k<n\le10^5$

HINT

如果你想要排序, 可以通过如下方法实现:

  • 包括头文件algorithm
  • 在命名空间内有sort(begin, end)函数, 其中beginend分别为排序开始的位置和结束的位置(左闭右开). 特别地, 如果想要让arr数组中下标为i至下标j之间(左闭右开)的元素从小到大排列的话, 可以调用sort(arr + i, arr + j)

例如:

#include <algorithm>
using namespace std;
int a[] = {3, 4, 1, 2};
int main() {
    sort(a + 1, a + 3);
    // 此时 a = {3, 1, 4, 2}
    sort(a, a + 4);
    // 此时 a = {1, 2, 3, 4}
    return 0;
}

需要注意的是,禁止使用<algorithm库内的其他函数.

zqy2018's solution

#include <cstdio>
#include <algorithm>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k;
int to[200005], at[100005], nxt[200005], cnt = 0;
int ans[100005], tot = 0;
int dfs(int cur, int fa){
    int maxi = 0, siz = 1;
    for (int i = at[cur]; i; i = nxt[i]){
        int v = to[i];
        if (v == fa) continue;
        int dd = dfs(v, cur);
        siz += dd;
        maxi = max(maxi, dd);
    }
    maxi = max(maxi, n - siz);
    if (maxi <= k) ans[++tot] = cur;
    return siz;
}
void init(){
    n = read(), k = read();
    for (int i = 1; i < n; ++i){
        int u = read(), v = read();
        to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
    }
}
void solve(){
    dfs(1, 0);
    if (tot == 0){
        printf("None\n");
    }else {
        sort(ans + 1, ans + tot + 1)    ;
        for (int i = tot; i > 1; --i)
            printf("%d ", ans[i]);
        printf("%d\n", ans[1]);
    }

}
int main(){
    init();
    solve();
    return 0;
}