题解：P5865 [SEERC 2018] Tree

Crewmateqaq · 2025-02-02 13:25:19 · 题解

题目大意

要在题目给出的有 n 个节点的一棵树上选取 m 个黑点，使最远的点对最小。

思路

进行暴力枚举。
多重循环,如果黑色点的个数超出了我们定义的变量 m，那么就将答案加入数组，最后再求最小值。

AC Code

#include <iostream>//超多的头文件，平时最好不要用万能头 
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstdio>
using namespace std;
#define ll long long//宏定义 
ll MAXX = 0x7fffffff;//一个超级超级超级大的数 
ll A[1000000],B[1000][1000];
int main()
{
    ll n,m,x,y,sum = MAXX,i,j,k;
    cin >> n >> m;
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= n;j++)
        {
            B[i][j] = MAXX;//初始化 
        } 
    } 
    for(i = 1;i <= n;i++) 
    {
        cin >> A[i];
        B[i][i] = 0;//将B数组要清零的地方清零 
    }
    for(i = 1;i < n;i++) 
    {
        cin >> x >> y;
        B[x][y] = B[y][x] = 1;
    }
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= n;j++)
        {
            for(k = 1;k <= n;k++)
            {
                B[j][k] = min(B[j][k],B[j][i] + B[i][k]);
            } 
        } 
    } 
    for(i = 1;i <= n;i++)//重要的一段，枚举 
    {
        for(j = i;j <= n;j++)//注意j要从i开始 
        {
            if(!A[j] || !A[i]) continue;
            ll ji = 0;
            for(k = 1;k <= n;k++)
            {
                if(A[k] && B[i][k] <= B[i][j] && B[k][j] <= B[i][j])
                {
                    ji++;//如果符合要求就加一 
                }
            }
            if(ji >= m)
            {
                sum = min(sum,B[i][j]);//把sum更新 
            } 
        }
    }
    cout << sum;
    return 0;//完结撒花 
}