KD-Graph HDU - 6958（多校第一场）

题目：KD-Graph

vjudge提交链接

官方题解：

签到题，将边按权值从小到大排序，
每一阶段取出同权值的所有边，
将这些边的端点用并查集两两合并，
若某一阶段的全部边合并完，并查集数量为k，
则当前阶段合并边的权值就是答案，
否则输出-1。反证法易证。

题意：

n个顶点，给出m条边的信息。现在问是否存在一个最小的D值恰好使原图变为k个连通的部分。

如何通过改变D值使原本不是k个连通的部分变为k个连通部分呢。

因为题目中给出了点与点连通的定义。

若顶点p和q (p≠q)连通，则p和q之间最长边小于或等于D（不是总路径长度）。

若点p和q (p≠q)不连通，则p和q之间最长边不可能小于或者等于D。

看样例说问题吧。
样例1的图：
样例2的图：
重新构造一个图：
因此当边权值相等时，小于或者等于D的边都必须是连通的，因此边权值相等的边必须一块进行合并，之后才能确定k值。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1e5+1100;
const int M=5*1e5+1100;
int f[N];
struct Node{
int u,v,w;
}q[M];
bool cmp(Node a,Node b){
return a.w<b.w;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=m;i++)
scanf("%d %d %d",&q[i].u,&q[i].v,&q[i].w);
sort(q+1,q+1+m,cmp);
for(int i=1;i<=n;i++)	f[i]=i;
q[0].u=-111,q[0].v=-11,q[0].w=-1111;
int total=n,ans=0;
for(int i=1;i<=m;i++)
{
if(q[i].w!=q[i-1].w)
{
if(total==k)
break;
}
int tu=find(q[i].u);
int tv=find(q[i].v);
if(tu==tv)	continue;
total--;
f[tv]=tu;
ans=q[i].w;
}
if(total==k)
printf("%dn",ans);
else
printf("-1n");
}
return 0;
}

最后

以上就是幸福白昼为你收集整理的KD-Graph HDU - 6958（多校第一场）的全部内容，希望文章能够帮你解决KD-Graph HDU - 6958（多校第一场）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。