自动搬运

查看原文

来自洛谷，原作者为

	XAVlER Xavier/ Pakalu Papito

搬运于2025-08-24 22:15:04，当前版本为作者最后更新于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

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

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