「HNOI2006」公路修建问题 - 二分+生成树

题目大意

OI island有$n$个旅游景点，不妨将它们从$1$到$n$标号。现在，OIER Association需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。
OIER Association打算修$n-1$条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率, OIER Association希望在这$n-1$条公路之中,至少有$k$条$(0\le k\le n-1)$一级公路。OIER Association也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。
而你的任务就是，在给定一些可能修建的公路的情况下，选择$n-1$条公路，满足上面的条件。

---

题目分析

最大值最小化，很显然使用二分转化为判定性问题。
考虑得到答案$mid$，那么先将$\le mid$的一级公路加入生成树，若加入的一级公路数量$\le k$，判定为失败。
一级公路加入生成树后，再将$\le mid$的二级公路加入生成树。
若最后生成树连通图，判定为成功。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=10005;
int n,m,k,father[maxn];
struct Edge {
	int from,to,dist;
	Edge(int x=0,int y=0,int v=0):from(x),to(y),dist(v) {}
	bool operator < (const Edge& b) const {
		return dist<b.dist;
	}
} edges1[maxn*2],edges2[maxn*2];
int Get_Father(int x) {
	if(father[x]==x)return x;
	return father[x]=Get_Father(father[x]);
}
bool Check(int Limit) {
	int cnt=0;
	for(int i=1; i<=n; i++)father[i]=i;
	for(int i=1; i<=m; i++) {
		if(edges1[i].dist>Limit)break;
		int fx=Get_Father(edges1[i].from),fy=Get_Father(edges1[i].to);
		if(fx!=fy) {
			father[fx]=fy;
			cnt++;
		}
	}
	if(cnt<k)return false;
	for(int i=1; i<=m; i++) {
		if(edges2[i].dist>Limit)break;
		int fx=Get_Father(edges2[i].from),fy=Get_Father(edges2[i].to);
		if(fx!=fy) {
			father[fx]=fy;
			cnt++;
		}
	}
	return cnt==n-1;
}
int main() {
	n=Get_Int();
	k=Get_Int();
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),c1=Get_Int(),c2=Get_Int();
		edges1[i]=Edge(x,y,c1);
		edges2[i]=Edge(x,y,c2);
	}
	sort(edges1+1,edges1+m+1);
	sort(edges2+1,edges2+m+1);
	int Left=0,Right=300000000;
	while(Left<=Right) {
		int mid=(Left+Right)>>1;
		if(Check(mid))Right=mid-1;
		else Left=mid+1;
	}
	printf("%d\n",Left);
	return 0;
}