BZOJ 1196 [HNOI2006]公路修建问题

题目大意

给你一个无向图，图上初始无边，求一个最小瓶颈生成树使得其中至少有K条指定的边。

按照先一级后二级，从小到大排序，之后二分瓶颈跑就好了= =

#include <cstdio>
#include <algorithm>
using namespace std;
int n,k,m,l,r,mid,inx,iny,ina,inb,fa[10010],tot;
struct edge
{
    int u,v,val,md;
}e[40010];
bool cmp(edge tx,edge ty)
{
    if(tx.md==ty.md) return tx.val<ty.val;
    return tx.md<ty.md;
}
int unifind(int tx) {return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}
void addedge(int tx,int ty,int ta,int tb)
{
    e[++tot].u=tx,e[tot].v=ty,e[tot].val=ta,e[tot].md=1;
    e[++tot].u=tx,e[tot].v=ty,e[tot].val=tb,e[tot].md=2;
}
bool check(int tg)
{
    int cnt=0;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<m;++i)
        if(e[i].val<=tg)
        {
            int tx=unifind(e[i].u),ty=unifind(e[i].v);
            if(tx!=ty)
            {
                fa[tx]=ty;
                ++cnt;
            }
        }
    if(cnt<k) return false;
    for(int i=m;i<=tot;++i)
    {
        if(cnt==n-1) return true;
        if(e[i].val<=tg)
        {
            int tx=unifind(e[i].u),ty=unifind(e[i].v);
            if(tx!=ty)
            {
                fa[tx]=ty;
                ++cnt;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<m;++i) scanf("%d%d%d%d",&inx,&iny,&ina,&inb),addedge(inx,iny,ina,inb);
    sort(e+1,e+tot,cmp);
    l=0,r=30001,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",r);
    return 0;
}