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

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

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;
}

• 相关文章