[HNOI2006]公路修建问题 (二分答案,并查集)

题目链接

Solution

二分答案+并查集.

由于考虑到是要求花费的最小值,直接考虑到二分.

然后对于每一个二分出来的答案,模拟 \(Kruskal\) 的过程再做一遍连边.

同时用并查集维护联通块信息.

最后看连的边数以及\(1\)边是否满足要求即可.

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=20008;

int n,k,m,v[maxn];

struct sj

{int x,y,w1,w2,id;}a[maxn];

int fa[maxn],ans,pd[maxn];

int find(int x)

    {if(fa[x]==x)return x;else return fa[x]=find(fa[x]);}

void join(int x,int y)

    {x=find(x),y=find(y);if(x!=y)fa[x]=y;}

bool cmp(sj x,sj y){return x.w1<y.w1;}

int read()

{

	int f=1,w=0; char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

bool jud(int x)

{

    for(int i=1;i<=n;i++)fa[i]=i;int cnt=0,js=0;

    memset(v,0,sizeof(v));

    sort(a+1,a+m,cmp);

    for(int i=1;i<m;i++){

        if(find(a[i].x)!=find(a[i].y))

                    if(a[i].w1<=x)cnt++,join(a[i].x,a[i].y),v[a[i].id]=1;}

    if(cnt<k)return 0;

    for(int i=1;i<m;i++)

    {

        if(!v[a[i].id])

        if(find(a[i].x)!=find(a[i].y))

            if(a[i].w2<=x)cnt++,join(a[i].x,a[i].y),v[a[i].id]=2;

    }

    if(cnt<n-1)return 0;

    for(int i=1;i<m;i++)

    pd[i]=v[i];

    return 1;

}

int main()

{

    n=read(),k=read(),m=read();

    for(int i=1;i<m;i++)

    {a[i].x=read();a[i].y=read();a[i].id=i;

    a[i].w1=read();a[i].w2=read();}

    int l=1,r=maxn*20;

    while(l<=r)

    {

        int mid=(l+r)/2;

        if(jud(mid)){ans=mid,r=mid-1;}

        else l=mid+1;

    }

    printf("%d\n",ans);

    for(int i=1;i<m;i++)

    if(pd[i])

        printf("%d %d\n",i,pd[i]);

}

巴特西

[HNOI2006]公路修建问题 (二分答案,并查集)

题目链接

Solution

Code

最新文章

热门文章