CCF201812_4,数据中心

就是最小生成树的模板算法，在中间过程中记录路径最大值即可，注意的是卡数据结构，邻接矩阵肯定是不行的，要选择开辟空间灵活一点的

#include<cstdio>
#include<queue>
#include <cstring>
//#include<map>
#include <algorithm>
#include <map>using namespace std;
struct cv{
    int len{
    };int a{
    },b{
    };cv(){
    }cv(int _len,int _a,int _b):len(_len),a(_a),b(_b){
    }bool operator ==(const cv&p)const{
    return a==p.a && b==p.b;}bool operator < (const cv &a)const{
    return len<a.len;}
};int n,m,root;#define maxn 50003
int parent[maxn];
cv e[maxn*2+1];int find(int a){
    int x = a;while(parent[x]!=x){
    x = parent[x];}while(parent[a]!=x){
    int tmp = parent[a];parent[a]=x;a = tmp;}return x;
}int main() {
    scanf("%d%d%d",&n,&m,&root);int l,r;for(int i = 1;i<=n;i++){
    parent[i] = i;}for(int i = 0;i<m;i++){
    int len;scanf("%d%d%d",&l,&r,&len);e[i] = cv(len,l,r);}sort(e,e+m);int res = 0;int pnum=0;for(int i = 0 ;i<m;i++){
    int l = e[i].a;int r = e[i].b;int pl = find(l);int pr = find(r);if(pl != pr){
    parent[pl] = pr;res = max(res,e[i].len);pnum++;}if(pnum == n-1){
    break;}}printf("%d\n",res);return 0;
}