BZOJ 2654: tree Kruskal+二分答案

2023-07-28 18:03:10

2654: tree

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 1863 Solved: 736
[Submit][Status][Discuss]

Description

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。

题目保证有解。

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。

V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

HINT

原数据出错，现已更新 by liutian,但未重测---2016.6.24

Source

想法：给全部白边加上同一个数，可以让白边在Kruskal中的加入顺序平移一下，那么白边数量也随之改变。

边权比较小，可以暴力枚举这个数O(200*m).发现这个数越大，白边数越少，于是二分优化。O(m*log200)

#include<cstdio>

#include<algorithm>

const int len(),lem(),INF(0x7fffffff);

int V,E,need,a,b,c,col,f[len+],limt,total,bf,ans,sum,last;

struct Node{int a,b,c;}white[lem+],black[lem+];int Wt,Bt;

bool cmp(Node A,Node B){return A.c<B.c;}

template <class T>void read(T &x)

{

    x=;char ch=getchar();int f=;

    while(ch<''||ch>''){f=(ch=='-');ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    x=f?-x:x;

}

int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}

bool union_fa(int x,int y)

{

    x=gf(x),y=gf(y); f[x]=y; return (x!=y);

}

void Kruskal()

{

    total=sum=; int Wl=,Bl=;

    for(int i=;i<=V;i++)f[i]=i;

    while(Wl<=Wt || Bl<=Bt)

    {

        if(Wl<=Wt && (white[Wl].c+limt<=black[Bl].c || Bl>Bt))

        {

            if(union_fa(white[Wl].a,white[Wl].b))total++,sum+=white[Wl].c;

            Wl++;

        }else

        {

            if(union_fa(black[Bl].a,black[Bl].b))sum+=black[Bl].c;

            Bl++;

        }

    }

}

int main()

{

//    freopen("C.in","r",stdin);

//    freopen("C.out","w",stdout);

    read(V),read(E),read(need);

    for(int i=;i<=E;i++)

    {

        read(a),read(b),read(c),read(col);a++,b++;

        if(col)black[++Bt]=(Node){a,b,c};

        else white[++Wt]=(Node){a,b,c};

    }

    std::sort(white+,white++Wt,cmp);

    std::sort(black+,black++Bt,cmp);

    limt=;

    for(int l=-,r=;l<=r;)

    {

        limt=(l+r)/; Kruskal();

        if(total>=need)ans=sum,l=limt+;else r=limt-;

    }

    printf("%d",ans);

    return ;

}

码农公寓