KD-Graph（hdu2021第一场）

46 阅读 0 评论 31 点赞

我是靠谱客的博主活力招牌，最近开发中收集的这篇文章主要介绍KD-Graph（hdu2021第一场），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

KD-Graph
题目链接：
link.
Problem Description
Let’s call a weighted connected undirected graph of n vertices and m edges KD-Graph, if the
following conditions fulfill:

n vertices are strictly divided into K groups, each group contains at least one vertice
if vertices p and q ( p ≠ q ) are in the same group, there must be at least one path between p and q meet the max value in this path is less than or equal to D.
if vertices p and q ( p ≠ q ) are in different groups, there can’t be any path between p and q meet the max value in this path is less than or equal to D.

You are given a weighted connected undirected graph G of n vertices and m edges and an integer K.

Your task is find the minimum non-negative D which can make there is a way to divide the n vertices into K groups makes G satisfy the definition of KD-Graph.Or −1 if there is no such D exist.

Input
The first line contains an integer T (1≤ T ≤5) representing the number of test cases.
For each test case , there are three integers n,m,k(2≤n≤100000,1≤m≤500000,1≤k≤n) in the first line.
Each of the next m lines contains three integers u,v and c (1≤v,u≤n,v≠u,1≤c≤109) meaning that there is an edge between vertices u and v with weight c.

Output
For each test case print a single integer in a new line.

Sample Input
2
3 2 2
1 2 3
2 3 5
3 2 2
1 2 3
2 3 3

Sample Output
3
-1
题意：

n个顶点严格分为K组，每组至少包含一个顶点
如果顶点 p 和 q ( p ≠ q ) 在同一组中，则 p 和 q 之间必须至少有一条路径满足该路径中的最大值小于或等于 D。
如果顶点 p 和 q ( p ≠ q ) 在不同的组中，则 p 和 q 之间不可能有任何路径满足该路径中的最大值小于或等于 D。

题解（并查集）：
需要找到最小的非负 $D$ ，它可以使有一种方法将 $n$ 个顶点分成 $K$ 个组，所以，需要使用到并查集，并根据权值进行结构体排序。可以将较小的 $n - k + 1$ 分为一个组，剩下的 $k - 1$ 个各为一组，如果两个点的父节点不同，则将两点两点合并在一个集合，否则跳过。当合并两点时，还需要将点数减一，且每次合并都能找到比上一次更小的 $D$ ，用 $a n s$ 记录更新.最后判断看是否存在这么一个 $D$ 满足要求。

#include<bits/stdc++.h>
using namespace std;
struct node
{
int u,v,c;
}a[500010];
int cmp(node x,node y)
{
return x.c<y.c;
}
int fa[500010];
int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&a[i].u,&a[i].v,&a[i].c);
}
for(int i=1;i<=n;i++)fa[i]=i;
sort(a+1,a+1+m,cmp);
int now=n;
int ans=0;
for(int i=1;i<=m;i++)
{
int u=a[i].u,v=a[i].v,c=a[i].c;
if(now==k&&c!=a[i-1].c)break;
if(find(u)==find(v))continue;
fa[find(u)]=find(v);
ans=c;
now--;
}
if(now!=k)cout<<"-1"<<endl;
else cout<<ans<<endl;
}
}