题解：P5865 [SEERC 2018] Tree

题目大意：

给定

n

个节点的边权为 1 的无向图，其中包括黑色节点和白色节点。选取至少

m

个黑色节点，使得任意两个黑色节点之间的最短路最大值最小。

思路：

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

m

个黑色节点（算上选取的两个节点）就更新答案，答案为选取的两个节点的最短路径长度。

代码：

CPP

#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;
}

题解：P5865 [SEERC 2018] Tree

文章操作

题目大意：

思路：

代码：

相关推荐

评论

题解：P5865 [SEERC 2018] Tree