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

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

煞笔的煞笔又来发水题题解了!

二分答案。先判一级公路然后判二级公路。没了。

1A什么的不必多说。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct E{ int u,v,c1,c2;}e[20005];
inline bool C(E a,E b){ return a.c1<b.c1;}
int F[10005],n,k,m; char buf[2000000],*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(){
    fread(pt,1,2000000,stdin);  int i;
    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;
}
Avatar_small
uburt.in 说:
2023年6月08日 20:39

Following verification, you must give a copy of your Aadhar card that has been self-attested.You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, uburt.in when creating an account on any KRA's eKYC site. Following verification, you must give a copy of your Aadhar card that has been self-attested. You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, when creating an account on any KRA's eKYC site.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter