Tree

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1668 字
二分白边附加权值后跑Kruskal
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1491
// 题意：无向带权图每条边是黑色或白色，求一棵恰好含 need 条白边的最小权生成树，点从 0 开始编号。
// 思路：给所有白边的权值统一加上增量 mid 后跑 Kruskal，白边条数随 mid 单调不增，二分出白边数恰好为 need 的 mid，答案再减去 need*mid。
// 复杂度：O(E log E log W) 时间 / O(V+E) 空间
// 易错点：权值相同时排序要让白边优先，否则二分边界处白边条数会抖动；累加的是加过 mid 的权值，最后要减掉 need*mid 还原成真实花费。
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 50005;
const int MAXE = 100005;
struct Edge{
    int u, v, w, c;
};
Edge e[MAXE];
int fa[MAXV];
int V, E, need;
int delta;
long long total;
int cntWhite;
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool cmpEdge(const Edge &a, const Edge &b){
    long long wa = a.w + (a.c == 0 ? delta : 0);
    long long wb = b.w + (b.c == 0 ? delta : 0);
    if(wa != wb) return wa < wb;
    return a.c < b.c;
}
int calc(int d){
    delta = d;
    sort(e, e + E, cmpEdge);
    for(int i = 0; i < V; i++) fa[i] = i;
    total = 0;
    cntWhite = 0;
    int cnt = 0;
    for(int i = 0; i < E; i++){
        int a = find(e[i].u);
        int b = find(e[i].v);
        if(a == b) continue;
        fa[a] = b;
        total += e[i].w + (e[i].c == 0 ? delta : 0);
        if(e[i].c == 0) cntWhite++;
        cnt++;
        if(cnt == V - 1) break;
    }
    return cntWhite;
}
int main(){
    if(!(cin >> V >> E >> need)) return 0;
    for(int i = 0; i < E; i++) cin >> e[i].u >> e[i].v >> e[i].w >> e[i].c;
    int l = -105, r = 105, best = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        if(calc(mid) >= need){
            best = mid;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    calc(best);
    cout << total - 1LL * need * best << '\n';
    return 0;
}
Tree

正文

一本通·提高篇的其它内容
