题解：P2619 [国家集训队] Tree I

Filberte · 2024-09-14 14:52:42 · 题解

题目链接

思路

看到好多题解都提到了二分，但似乎没有严谨地证明 wqs 二分中函数的凸性，在这里介绍另外一种理解方法。

定义 G(c) 表示每条白边边权加了 c 之后的图，w(c,T) 表示在 G(c) 中 T 这棵生成树上的边权和。

• 引理 1：若对于某个 c，G(c) 的最小生成树 T 有 k 条白边，那么在 G 中取 T 中的边构成的树是最小生成树。
• 证明 1：假如存在另一棵树 T' 比 T 更优，则 w(0,T') < w(0,T)，可以推出 w(0,T') + kc < w(0,T) + kc，也就是说 w(c,T') < w(c,T)，与 T 是 G(c) 的最小生成树矛盾。
• 引理 2：G 中最小生成树的白边数是一个连续的区间。
• 证明 2：考虑克鲁斯卡尔算法的过程，按边权分阶段，在同一阶段内取到的白边数肯定是一个连续区间，而每个阶段都是连续区间，所以最后也是一个连续区间。
• 引理 3：设 G(c) 的白边数量是 [l_c,r_c]，那么 r_c = l_{c - 1}。
• 证明 3：按权值排序，权值相同的按颜色排序，权值和颜色都相同的进入同一个集合。假如目前有集合 B_1,W_1,B_2,W_2\dots B_x,W_x。 r_c 会尽量优先选白边，选出 W_1',B_1'\dots W_x',B_x' 这样的集合，其中 W_i'\subseteq W_i,B_{i}' \subseteq B_i。原本 B_i 中元素权值与 W_{i} 中元素权值向同，但当所有白边的权值都减一之后，W 的优先级就比同级的 B 更高了，此时还是选出 W_1',B_1'\dots W_x',B_x' 这样的集合。

有了引理 3，二分变得可行。之后的内容较为显然，在此不再赘述。

代码

#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 100;
const int N = 5e4 + 100;
struct E{
    int u, v, w, c;
    bool operator < (E ot)const{
        return w != ot.w ? w < ot.w : c < ot.c;
    }
}e[M];
int n, m, ned, ans;
int fa[N];
int find(int x){return x == fa[x] ? x : (fa[x] = find(fa[x]));}
int sum, cnt, wt;
void kruskal(){
    for(int i = 1;i <= n + 1;i++) fa[i] = i;
    sum = cnt = wt = 0;
    sort(e + 1, e + 1 + m);
    for(int i = 1;i <= m;i++){
        int u = find(e[i].u), v = find(e[i].v);
        if(u == v) continue;
        fa[u] = v;
        sum += e[i].w;
        if(!e[i].c) wt++;
        if(++cnt == n - 1) break;
    }
}
int main(){
    cin >> n >> m >> ned;
    for(int i = 1;i <= m;i++){
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        e[i] = {u + 1, v + 1, w, c};
    }
    int l = -101, r = 101;
    while(l <= r){
        int mid = (l + r) >> 1;
        for(int i = 1;i <= m;i++) if(!e[i].c) e[i].w += mid;
        kruskal();
        if(wt >= ned) l = mid + 1, ans = sum - ned * mid;
        else r = mid - 1;
        for(int i = 1;i <= m;i++) if(!e[i].c) e[i].w -= mid;
    } 
    cout << ans << endl;
    return 0;
}