题解

XAVlER · 2023-07-02 16:11:02 · 题解

P5865

错了好几次才AC QAQ

读题：

给定一棵 n 个点的树，点的编号从 1 到 n。每个点有黑色或白色的颜色。选出恰好 m 个黑点，使得黑点两两之间的距离的最大值最小。输出这个最小的最大值。

题意：有一棵树，在它上面 n 个节点中选取 m 个黑点，求最远的点对的最小值。

本题不难，只要枚举即可。假设两点之间的距离为树的端点，然后再去枚举其他点，符合的加入集合。若黑色点的个数超出了定义个数，那么就更新一遍。最后求最小值。

36行，供参考：

AC Code:

#include <bits/stdc++.h> //保命万能头
using namespace std; //命名空间
const int INF=0x3f3f3f3f; //方便后续使用
int main()
{
    int n,m,x,y,c[101][101],a[101],ans=INF;
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=INF;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i]; //输入
        c[i][i]=0;
    }
    for(int i=1;i<n;i++) 
    {
        cin>>x>>y; //还是输入
        c[x][y]=c[y][x]=1;
    }
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
    //开始枚举
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(!a[j]||!a[i]) continue;
            int cnt=0; //初始化计数器
            for(int k=1;k<=n;k++)
            {
                if(a[k]&&c[i][k]<=c[i][j]&&c[k][j]<=c[i][j]) cnt++; //计数
            }
            if(cnt>=m) ans=min(ans,c[i][j]); //求最小值
        }
    }
    cout<<ans; //输出结果ans
    return 0; //好习惯
}
//P.S.求过！

运行结果result

attention

仅供参考,请在理解后食用。

（好人做到底，点个赞呗）