最小生成树：Tree

参考资料：https://blog.csdn.net/sunshinezff/article/details/48749453

Description

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

Input

　　第一行V,E,need分别表示点数，边数和需要的白色边数。
　　接下来E行
　　每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

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

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2
HINT

数据规模和约定

　　0:V<=10

　　1,2,3:V<=15

　　0,..,19:V<=50000,E<=100000

　　所有数据边权为[1,100]中的正整数。
---------------------

题解摘抄：

显然可以发现随着白边权值的增大。最小生成树中白边的个数不增。

然后根据这个性质我们就可以二分一个值，然后每次给白边加上这个值。看一下最小生成树中白边的个数。

最后答案再把它减去。

看起来思路非常简单，但是有一个很重要的细节。

如果在你的二分过程中如果给白边加上mid,你得到的白边数比need大。

给白边加上mid+1,你得到的白边比need小。

这种情况看似没法处理。

但是考虑一下克鲁斯卡尔的加边顺序。

可以发现如果出现这种情况，一定是有很多相等的白边和黑边。因为数据保证合法。

所以我们可以把一些白边替换成黑边。

所以我们要在白边数>=need的时候跟新答案。

具体用ans=ans-mid*need;即可。

#include<bits/stdc++.h>

using namespace std;

struct node{

    int x,y,w,c;

}a[];

int pre[];

int v,e,need,s[],t[],c[],col[],m=;

int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);

}

bool cmp(node a,node b){

    if(a.w==b.w) return a.c<b.c;//关键点

    else

     return a.w<b.w;

}

int ans,tot;

int kruskal(int mid)

{

    int num=;

    memset(a,,sizeof a);

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

    {

        a[i].x=s[i];

        a[i].y=t[i];

        a[i].c=col[i];

        a[i].w=c[i];

        if(a[i].c==)

        {

            a[i].w+=mid;

        }

    }

    stable_sort(a+,a+e+,cmp);

    for(int i=;i<=v+;i++) pre[i]=i;//注意点

    int cnt=;

    tot=;

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

    {

        int fx=find(a[i].x);

        int fy=find(a[i].y);

        if(fx!=fy){

            cnt++;

            tot+=a[i].w;

            pre[fx]=fy;

            if(a[i].c==)

            {

                num++;

            }

            if(cnt==v-) break;

        }

    }

    return num;

}

int main()

{

    scanf("%d%d%d",&v,&e,&need);

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

    {

        scanf("%d%d%d%d",&s[i],&t[i],&c[i],&col[i]);

        s[i]++;t[i]++;

    }

    int l=-,r=;//注意点三

    while(l<=r)

    {

        int mid=(l+r)/;

        int a1=kruskal(mid);

        if(a1>=need)

        {

            l=mid+;

            ans=tot-mid*need;//关键点

        }

        else r=mid-;

    }

    cout<<ans;

    return ;

}

巴特西

最小生成树：Tree

最新文章

热门文章