题解：P5865 [SEERC 2018] Tree

Giorno_ · 2025-11-20 16:12:39 · 题解

题目大意：

给定 n 个节点的边权为 1 的无向图，其中包括黑色节点和白色节点。选取至少 m 个黑色节点，使得任意两个黑色节点之间的最短路最大值最小。

思路：

先根据题目建边，边权设 1。暴力枚举各个点之间的最短路（其实是 Floyd）。每次选举两个黑色节点最为最大长度，若路径上包括 m 个黑色节点（算上选取的两个节点）就更新答案，答案为选取的两个节点的最短路径长度。

代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 110;
int f[N][N];
int n,m,a[N],ans = 114514;
bool vis[N][N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    memset(f,0x3f3f3f,sizeof f);
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        f[i][i] = 0;
    }
    for(int i = 1;i < n;i ++){
        int x,y;
        cin >> x >> y;
        f[x][y] = 1;
        f[y][x] = 1;
    }
    for(int k = 1;k <= n;k ++)
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++){
            f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
        }
    for(int i = 1;i <= n;i  ++){
        for(int j = 1;j <= n;j ++){
            if(!a[i] or !a[j])continue;
            int cnt = 0;
            for(int k = 1;k <= n;k ++){
                if(a[k] and f[i][k] <= f[i][j] and f[k][j] <= f[i][j])
                //因为我们选择i j作为最长路径，因此要保证每个黑色节点与端点距离不超过最长路径 
                cnt ++;
            }
            if(cnt >= m)ans = min(ans,f[i][j]);
        }
    }dui 
    cout << ans; 
    return 0;
}