luogu P2619 [国家集训队2]Tree I

题目链接

luogu P2619 [国家集训队2]Tree I

题解

普通思路就不说了二分增量，生成树check

说一下坑点

二分时，若黑白边权有相同，因为权值相同优先选白边，若在最有增量时出现黑白等权边则更新出 > 和 = 最小值等价，那么不会更新到 = 情况，

因为等价，那么处理时只需看做把等价的黑白两边交换即可

需要每次直接减去 增量 * need 的价值

代码

#include<cstdio>

#include<algorithm>

const int maxn = 100007;

int E,V,need;

struct node {

    int u,v,w,col;

    bool operator < (const node & a) const {

        if(a.w == w) return col < a.col;

        else return w < a.w;

    }

}edge[maxn],e[maxn];

int ans = 0;

int fa[maxn];

int find(int x) {

    if(fa[x] != x) fa[x] = find(fa[x]);

    return fa[x];

}

bool check(int x) {

    int tmp = 0;

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

        e[i] = edge[i];

    if(e[i].col == 0) e[i].w = edge[i].w + x;

    }

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

    std::sort(e + 1,e + V + 1);int bs = 0;

    for(int num = 0,i = 1;i <= V;++ i) {

        int X = e[i].u,y = e[i].v;

        int fx = find(X),fy = find(y);

        if(fx != fy) {

            tmp += e[i].w;

            num ++;

            fa[fx] = fy;

            if(e[i].col == 0) bs ++;

        }

        if(num == E - 1) break;

    }

    if(bs >= need) {

        ans = tmp - (x * need);

        return true;

    }

    return false;

}

int main() {

    scanf("%d%d%d",&E,&V,&need);

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

        scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w,&edge[i].col);

    }

    int l = -107,r = 107;

    while(l <= r) {

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

        if(check(mid)) l = mid + 1;

        else r = mid - 1;

    }

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

    return 0;

}