[luogu]P2323 [HNOI2006]公路修建 kruskal+二分

前言

我就总感觉在哪里见过

相似传送门 ：

题目传送门 :

思路

其实这题也可以不用二分,我们可以直接排序先将前k条边放进去

然后再排序将n-k-1条边放进去

因此这样来就没必要二分了,具体看相似度传送门:

当然,最大值最小显然就是一个二分题目

所以我们也是可以用二分做的,我们可以二分出k每次都合并区间,然后查看是否满足条件即可

CODE

struct node
{
	int a,b,c1,c2;
}e[N];
int p[N];

int find(int x)
{
	return p[x] == x?x:p[x] = find(p[x]);
}

bool merge(int a,int b)
{
	a = find(a),b =find(b);
	if(a == b)return 0;
	p[a] =b;return 1;
}

bool check(int mid)
{
	int cnt = 0 ;
	for(int i=1;i>m;
	m--;
	for(int i=1;i>e[i].a>>e[i].b>>e[i].c1>>e[i].c2;
	
	int ans = binary(1,30000);
	cout