【bzoj2654】 tree

http://www.lydsy.com/JudgeOnline/problem.php?id=2654 (题目链接)

题意

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

solution

　　今天考试题，以为是神题不可做，直接放弃了。。没想到这么水。。我们考虑把白边的权值增加，因为无论白边的权值增加多少，最小生成树中的白边不会改变。所以我们二分每次把所有白边的权值增加多少，按边权大小排序后克鲁斯卡尔看选出的白边是否大于need。统计答案

细节

　　若黑白两边权值相同，优先选择白边加入最小生成树

代码

// bzoj2654

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=1000010;

struct edge {

    int u,v,w,c;

    friend bool operator < (const edge &a,const edge &b) {

        return a.w==b.w?a.c<b.c:a.w<b.w;

    }

}e[maxn];

LL fa[maxn],u[maxn],v[maxn],w[maxn],c[maxn],tot,cnt,n,m,ned,sumv;

int find(int x) {

    return x==fa[x]?x:fa[x]=find(fa[x]);

}

bool check(int x) {

    tot=cnt=0;

    for (int i=1;i<=n;i++) fa[i]=i;

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

        e[i].u=u[i],e[i].v=v[i],e[i].w=w[i],e[i].c=c[i];

        if (!c[i]) e[i].w+=x;

    }

    sort(e+1,e+m+1);

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

        int p=find(e[i].u),q=find(e[i].v);

        if (p!=q) {

            fa[p]=q;

            tot+=e[i].w;

            if (!e[i].c) cnt++;

        }

    }

    return cnt>=ned;

}

int main() {

    scanf("%lld%lld%lld",&n,&m,&ned);

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

        scanf("%lld%lld%lld%lld",&u[i],&v[i],&w[i],&c[i]);

        u[i]++;v[i]++;

    }

    int l=-10005,r=10005;

    while (l<=r) {

        int mid=(l+r)>>1;

        if (check(mid)) l=mid+1,sumv=tot-ned*mid;

        else r=mid-1;

    }

    printf("%lld",sumv);

    return 0;

}

巴特西

【bzoj2654】 tree

题意

solution

细节

代码

最新文章

热门文章