[luogu] P4047 [JSOI2010]部落划分 最小生成树||二分答案

前言

这也可以歪成这个hh 二分答案待补 传送门 :

思路

如果这个题,每个点看作一个部落的话 , 我们贪心的根据边排序, 将最大的边的部

部落算成一个集合,那么我们就可以跑一遍 k r u s k a l kruskal kruskal算法,那么这题的答案就是求第

n − k + 1 n-k+1 n−k+1条边,总之抽象有点喜感,

CODE

const int N  = 1e6+10;
int p[N];
int wx[N],wy[N];
int idx  ;
int n,m,k;



struct node
{
	int a,b;
	double c;
	
	bool operator