首页 > 试题广场 >

屠龙者

[编程题]屠龙者

热度指数：109 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小明是A村里的屠龙者，他一直保卫着村子的和平，以不受恶龙的侵扰。而恶龙们也对小明恨之入骨，于是恶龙们决定组织一次集体进攻，以打败小明，拿下A村。小明知道，恶龙集体进攻的时候，会在彼此之间建立一种神秘的链接，而被这种链接连接起来的恶龙能够增长彼此的能力，且每有一只恶龙加入到一个链接中，这个链接里的所有龙的能力都会加1，而只有当小明的战斗力大于龙的战斗力时，才能将龙杀死。万幸的是，小明有一把一次性的屠龙刀，他可以无视战斗力地杀死一只龙，并消除这条龙身上的所有链接。假设每条龙不被链接时的战斗力为1，初始时所有N只恶龙被N-1条链接连接在一起。小明想知道他至少要有多少的战斗力，才能将所有龙都杀死，同时他想知道，他应该用屠龙刀杀掉哪只龙。

输入描述:

输入的第一行是一个整数N(1<=N<=40000), 表示一共有N只龙。
接下来N-1行整数对a,b（以空格分隔），表示龙之间的链接关系

输出描述:

输出以空格分隔的两个整数。第一个整数X，表示应用屠龙刀杀死的龙的编号。若有多只龙都可被屠龙刀杀死，输出编号最小的那个
第二个整数T，表示小明至少需要有的战斗力

示例1

输入

输出

1 5

说明

初始时所有龙都在一个链接中，此时所有龙的战斗力都为8。当用屠龙刀杀死1号龙后，剩下的龙分别在两个链接中（2,3,4和5,6,7,8），此时5,6,7,8号龙战斗力皆为4；2,3,4号龙的战斗力为3，故小明的战斗力至少为5才可杀死所有龙。

算法知识视频讲解

gywy

求树的重心,只有一个节点的时候需要特判

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], idx;
int n;
int ans = N, id = N;
bool st[N];

int dfs(int u)
{
    int res = 0;
    int sum = 1;
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    if (res < ans)
    {
        ans = res;
        id = u;
    }
    else if (res == ans && u < id) id = u;

    return sum;
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int main()
{
    memset(st, 0, sizeof st);
    memset(h, -1, sizeof h);
    cin >> n;
    if (n == 1)
    {
        cout << 1 << ' ' << 0 << endl;
        return 0;
    }
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << id << ' ' << ans + 1 << endl;
    return 0;
}

编辑于 2020-03-15 17:46:40 回复(0)