[BZOJ1196][HNOI2006]公路修建问题 kruskal

原题链接
将所有边排序,弄两个并查集分别维护只有一级公路的连通性和算上二级公路的连通性即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10233
#define M 20233
using namespace std;
int n,k,m,tot,num1,num2;//边数/光白边边数
struct edge
{
    int x,y,z,col;
}e[M<<1];
inline void add(int x,int y,int z,int col)
{
    e[++tot].x=x,e[tot].y=y,e[tot].z=z,e[tot].col=col;
}
inline bool operator<(const edge &x,const edge &y)
{
    return x.z==y.z?(x.col<y.col):(x.z<y.z);
}
struct ufs
{
    int fa[N];
    void init()
    {
        for(int i=1;i<=n;++i)fa[i]=i;
    }
    int find(int x)
    {
        return x==fa[x]?x:(fa[x]=find(fa[x]));
    }
    inline int merge(int x,int y)
    {
        x=find(x);y=find(y);
        if(x!=y)
        {
            fa[x]=y;
            return 1;
        }
        return 0;
    }
}a,b;//两个并查集 a维护连通性 b维护白边连通性
int main()
{
    cin>>n>>k>>m;
    m--;
    for(int x,y,z1,z2,i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&x,&y,&z1,&z2);
        add(x,y,z1,0);add(x,y,z2,1);
    }
    sort(e+1,e+tot+1);
    a.init();b.init();
    for(int i=1;i<=tot;++i)
    {
        num1+=a.merge(e[i].x,e[i].y);
        if(!e[i].col)num2+=b.merge(e[i].x,e[i].y);
        if(num1==n-1&&num2>=k)
        {
            printf("%d\n",e[i].z);
            return 0;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注