SEERC 2018 C Tree(floyd+暴力)

本文主要是介绍SEERC 2018 C Tree(floyd+暴力)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://codeforces.com/group/xrTA2IaQje/contest/254611/problem/C

 

题目大意：有n个点组成的一棵树，其中有若干个点是黑色的，要求选出m个黑点并求出他们之间最大距离的最小值

 

题目思路：一个重要性质，也就是当一棵树存在一个直径时，加入点能够满足这个直径还是直径只需要满足这个新加入的点到两个端点的距离不超过直径距离，所以直接暴力枚举两个端点，然后看能不能加入m个点，如果可以就更新答案

 

以下是代码：

#include<bits/stdc++.h>using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define inf 0x3f3f3f3f
const int MAXN = 102+5;
const int MOD = 1e9+7;
int n,m,p[MAXN],dis[MAXN][MAXN],x,y;
int main()
{while(~scanf("%d%d",&n,&m)){rep(i,1,n)scanf("%d",&p[i]);memset(dis,0x3f,sizeof(dis));rep(i,1,n)dis[i][i]=0;rep(i,1,n-1){scanf("%d%d",&x,&y);dis[x][y]=dis[y][x]=1;}rep(k,1,n){rep(i,1,n){rep(j,1,n){dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}}}int ans=inf;rep(i,1,n){rep(j,i,n){if(!p[i]||!p[j])continue;int num=0;rep(k,1,n){if(!p[k])continue;if(dis[i][k]<=dis[i][j]&&dis[j][k]<=dis[i][j]){num++;}if(num==m)break;}if(num==m)ans=min(ans,dis[i][j]);}}printf("%d\n",ans);}return 0;
}

 

这篇关于SEERC 2018 C Tree(floyd+暴力)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---