# BZOJ1196: [HNOI2006]公路修建问题【二分判定】

dzy posted @ 2013年6月09日 18:06 in BZOJ with tags BZOJ 二分 并查集 , 2202 阅读

1A什么的不必多说。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct E{ int u,v,c1,c2;}e;
inline bool C(E a,E b){ return a.c1<b.c1;}
int F,n,k,m; char buf,*pt=buf;
int GF(int x){  return x==F[x]?x:F[x]=GF(F[x]);}
inline int getint(){
int r=0;while(*pt<'0'||*pt>'9')pt++;while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline int ok(int lmt){
int ck=0,ca=0;
for(int i=1;i<=n;i++) F[i]=i;
for(int i=1;i<=m;i++){
if(e[i].c1<=lmt){
int u=GF(e[i].u),v=GF(e[i].v);
if(u!=v) F[u]=v,ck++,ca++;
if(ca==n-1) return 1;
}else{
if(ck<k) return 0;
if(min(e[i].c1,e[i].c2)>lmt) continue;
int u=GF(e[i].u),v=GF(e[i].v);
if(u!=v) F[u]=v,ca++;
if(ca==n-1) return 1;
}
}return 0;
}int main(){
for(n=getint(),k=getint(),m=getint(),i=1;i<m;i++)
e[i].u=getint(),e[i].v=getint(),e[i].c1=getint(),e[i].c2=getint();
sort(e+1,e+m+1,C);  int l=0,r=1000000009,mid;
while(l<=r){
mid=l+r>>1;
if(ok(mid)) r=mid-1;    else    l=mid+1;
}printf("%d\n",l);return 0;
} uburt.in 说:
2023年6月08日 20:39 