[Acwing] 1142.繁忙的都市 Kruskal性质题

前言

又又歪了hh 传送门 :

思路

一开始看数据范围直接想到了 p r i m prim prim,

才发现他需要求最小生成树的边最大值,(一看傻了,还要每次多记录一个量？

仔细想想其实 k r u s k a l kruskal kruskal也可以做,因为满足时间复杂度hh

而且这个算法本身就是对边进行排序,我们可以很容易的就知道

最后加进来的那条边一定就是最小生成树中边权最大的那一条

CODE

struct Edge
{
	int a,b,w;
	bool operatorm;
	for(int i=1;i>a>>b>>c;
		edge[i] = {a,b,c};
	}
	kruskal();
	cout