本文主要是介绍KD-Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目:
链接
题意:
总共有 n n n 个点, m m m条边,要分成 k k k 组,满足
( 1 ) (1) (1) 如果顶点 p 和 q ( p ≠ q ) 在同一组中，则 p 和 q 之间必须至少有一条路径满足该路径中的最大值小于或等于 D。
( 2 ) (2) (2) 如果顶点 p 和 q ( p ≠ q ) 在不同的组中，则 p 和 q 之间不可能有任何路径满足该路径中的最大值小于或等于 D。
题解:
最开始分为 c n t = n cnt=n cnt=n个组
按找点的边权从小到大排序, 如果这两个点不在同一个集合中,则将它们合并到一个集合中,同时 c n t − = 1 cnt-=1 cnt−=1,(减少了只有一个点的组), 当 c n t = k cnt=k cnt=k的时候, D D D为当前的边权值,否则为 − 1 -1 −1
注意为了满足要求(2),只有当当前边权不等于上一个边权的时候才判断 c n t cnt cnt是否等于 k k k
#include <bits/stdc++.h>
using namespace std;
struct node {long long u,v,w;
}e[500005];
int p[100005];
bool cmp(node a,node b)
{return a.w<b.w;
}
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){int n,m,k;cin>>n>>m>>k;int ans=0;int con=n;for(int i=1;i<=n;i++) p[i]=i;for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].w;}sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++){if(e[i].w!=e[i-1].w)//满足要求(2){if(con==k){break;}}int pa=find(e[i].u);int pb=find(e[i].v);if(pa==pb) continue;con--;p[pa]=pb;ans=e[i].w;//D为当前的边权值}if(con==k) cout<<ans<<endl;else cout<<-1<<endl;}return 0;
}
这篇关于KD-Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
