首页 > 代码库 > [bzoj1196][HNOI2006]公路修建问题

[bzoj1196][HNOI2006]公路修建问题

给定一个n个点m条边的图,每条边都有两个等级,分别要c1和c2费用。你需要构造一个最小生成树,并且满足最少有k条一级边。

n,k<=10000,m<=20000

题解:很自然的想到二分一个答案,然后先连一级边,再连二级边,判断能否连通/是否有足够的一级边 就可以啦。

复杂度mlogMAXC

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-) f=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0; ch=getchar();}
    return x*f;
}

int n,m,K,s[10005];
struct edge{
    int from,to,w;
}c1[20005],c2[20005];
bool cmp(edge x,edge y){return x.w<y.w;}
int getfa(int x){return s[x]==0?x:s[x]=getfa(s[x]);}

bool check(int mid)
{
    memset(s,0,sizeof(s));int num=1,cnum=0,x,y;
    for(int i=1;i<=m&&c1[i].w<=mid;i++)
        if((x=getfa(c1[i].from))!=(y=getfa(c1[i].to)))
            s[x]=y,num++,cnum++;
    if(cnum<K)return false;
    for(int i=1;i<=m&&c2[i].w<=mid;i++)
        if((x=getfa(c2[i].from))!=(y=getfa(c2[i].to)))
            s[x]=y,num++;
    return num==n;
}

int main()
{
    n=read();K=read();m=read();
    for(int i=1;i<m;i++)
    {
        c1[i].from=c2[i].from=read();
        c1[i].to=c2[i].to=read();
        c1[i].w=read();c2[i].w=read();
    }
    sort(c1+1,c1+m+1,cmp);sort(c2+1,c2+m+1,cmp);
    int l=1,r=30000,mid,ans;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

 

[bzoj1196][HNOI2006]公路修建问题