KD-Graph

53 阅读 0 评论 35 点赞

我是靠谱客的博主甜甜冬瓜，最近开发中收集的这篇文章主要介绍KD-Graph，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

3 2 2

1 2 3

2 3 5

3 2 2

1 2 3

2 3 3

Sample Output

3
-1

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1e6+10;
int T,n,m,k,fa[maxn],now,ans;
struct da{int u,v,w;}q[maxn];
bool cmp(da aa,da bb){return aa.w<bb.w;}
int getf(int x)
{
if (fa[x]==x) return x;
fa[x]=getf(fa[x]);
return fa[x];
}
void solve()
{
scanf("%d%d%d",&n,&m,&k); now=n; ans=0;
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++) scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
sort(q+1,q+m+1,cmp);
for (int i=1;i<=m;i++)
{
if (q[i].w!=q[i-1].w){if (now==k) {printf("%dn",ans); return;}}
if (getf(q[i].u)==getf(q[i].v)) continue;
now--; fa[getf(q[i].u)]=getf(q[i].v); ans=q[i].w;
}
printf("%dn",now==k?ans:-1);
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
scanf("%d",&T);
while (T--) solve();
return 0;
}