欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CCF 数据中心

程序员文章站 2024-02-28 17:35:58
...
/*---克鲁斯卡尔算法---*/
//其实题意就是找最小生成树中的最大的边 
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXV=50001;//最大顶点数 
const int MAXE=100001;

struct edge{//边的结构体 
	int u,v;
	int cost;
}E[MAXE];

bool cmp(edge a,edge b){
	return a.cost<b.cost;
}

int father[MAXV];//并查数组集 
int findFather(int x){//并查集查询函数 
	int a=x;
	while(x!=father[x]){
		x=father[x];
	}
	//路径压缩 
	while(a!=father[a]){
		int z=a;
		a=father[a];
		father[z]=x;
	}
	return x;
}
//克鲁斯卡尔部分,返回最小生成树的边权之和,n个顶点,m条边 
int kruskal(int n,int m){
	//ans为生成树权值,Num_Edge为生成树的边数 
	int ans=0,Num_Edge=0;
	for(int i=1;i<=n;i++){//顶点范围从1--n 
		father[i]=i;//并查集初始化 
	}
	sort(E,E+m,cmp);
	for(int i=0;i<m;i++){//枚举所有边 
		int faU=findFather(E[i].u);//查询测试两个端点所在集合的根节点 
		int faV=findFather(E[i].v);
		if(faU!=faV){//若不在一个集合中 
			father[faU]=faV;//合并集合 
			if(E[i].cost>ans)ans=E[i].cost; //使ans变成最大的边 
			Num_Edge++;//边数+1 
			if(Num_Edge==n-1)break;//边数等于顶点数-1时跳出 
		}
	}
	
	if(Num_Edge!=n-1)return -1;
	else return ans;
}

int main(){
	int n,m;
	int u,v,w,s; 
	cin>>n>>m>>s;
	
	for(int i=0;i<m;i++){//输入图 
		cin>>E[i].u>>E[i].v>>E[i].cost;
	}
	
	int ans=kruskal(n,m);
	cout<<ans;
}