题解：P5865 [SEERC 2018] Tree

Gardener2015 · 2026-06-07 08:30:42 · 题解

思路

因为数据范围小，所以我们先用 Floyd 求出任意两点之间的最短路，然后暴力枚举任意两个黑点，假设现在枚举的两个点 i 和 j 之间的距离为答案，那么再枚举一个黑点 k，如果 k 到点 i 和点 j 的距离都不大于当前假设的最长距离，那么这个点就是合法的，将合法点的数量加一，如果合法点的数量不小于 m，那么 i 和 j 之间的距离就可以成为答案，与答案取最小值即可，最后输出答案。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,dis[101][101],p[101],ans=2147483647,cnt;//注意答案要初始化成一个较大值，才能保证答案正确
int main(){
    cin>>n>>m;
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        dis[u][v]=1;
        dis[v][u]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i==j)
                    dis[i][j]=0;
                else
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            if(p[i]&&p[j]){
                cnt=0;
                for(int k=1;k<=n;k++)
                    if(p[k]&&dis[i][k]<=dis[i][j]&&dis[j][k]<=dis[i][j])//k必须是黑点
                        cnt++;
                if(cnt>=m)
                    ans=min(ans,dis[i][j]);
            }
    cout<<ans<<endl;
    return 0;
}