题解 CF125E 【MST Company】

· · 题解

这里主要讲下 wqs 二分没法正好二分出需要的最小生成树方案时该如何构造方案

解析

题意以及前面基本的 wqs 二分部分就直接略过了

考虑为什么我们无法直接二分出需要的最小生成树方案：此时函数的最小值实际上不再是一个点，而是一段区间，设其为 [l, r]

这实际上就代表，在当前的图上（所有与 1 相连的边的边权加上该次二分的 C 值后的图），选择 k, l\leq k\leq r 条与 1 相连的边的最小生成树方案都是存在的

接着我们直接给出（也可以认为由生成树的性质而启发得到的...）构造的方法：

（下面为了方便，均将 “与 1 结点相连的边” 称为 “特殊边”）

设要求构造的方案需要 k 条特殊边，在 “当前图” 上的最小生成树的每种边权 val 至少要用 c_{val} 条特殊边（若要得到 c_{val}，只需在排序上动手脚：使相同边权的其它边排在特殊边前面，这样就尽量避免了选特殊边）

在做 Kruskal 时（尚不清楚是否有基于 prim 的构造方法...），我们记录已经选择的特殊边的数量 \text{cnt}（补充：在第二种方案中的定义可能有些不同...），并以相同边权的边为一组

一种方案是：在做每一组时，先尝试使用特殊边，如果可行，且 k-\sum\limits_{val} c_{val}+c_{now}-(\text{cnt}-\sum\limits_{val\in Pre} c_{val})>0（其中 Pre 指已经处理过（不含当前）的组的边权集合，c_{now} 指当前正处理的颜色的 c），就选择这条边。处理完特殊边后再尝试使用非特殊边

另一种方案是：先找出一种选择特殊边最少的最小生成树方案 S。在做每一组时，我们先将 S 中存在的特殊边先连上（注意不要连非特殊边），并且不计入 \text{cnt}，之后依然先尝试使用特殊边；如果可行，且 k-\text{cnt}>0，那么就选择这条边。处理完特殊边后再尝试使用非特殊边。这种构造方式应该会更好理解

最后考虑证明这种构造方式

事实上，我们可以发现这种构造方式和原来的 Kruskal 算法是没有本质区别的...；且目标的生成树方案已经保证存在，因此该构造方式一定有解

CODE

代码里可能显式或隐式地将 与 1 结点相连的边 称为 “白边”，将 除此以外的其它边 称为 “黑边”

另外代码里用的是后一种构造方式

仅供参考，有些地方的实现可能很烂

#include <cstdio>
#include <algorithm>
using std::sort;

const int MAXN =5e3+20, MAXM =1e5+20;

/*------------------------------Disjoint Set------------------------------*/

int fa[MAXN], rank[MAXN];

int get_root(const int &x){
    if(fa[x] == x)
        return x;
    else
        return fa[x] =get_root(fa[x]);
}

inline void merge(int x, int y){
    x =get_root(x), y =get_root(y);
    if(rank[x] == rank[y])
        ++rank[x];
    else if(rank[x] < rank[y])
        rank[y] ^=rank[x] ^=rank[y] ^=rank[x];
    fa[y] =x;
}

void clear_disjointSet(const int &n){
    for(int i =1; i <= n; ++i)
        fa[i] =i, rank[i] =0;
}

/*------------------------------Kruskal------------------------------*/

struct edge{
    int u, v, w, id;
    bool col;
}e_b[MAXM], e_w[MAXM], e_qaq[MAXM];
int totb, totw, tot;

bool cmp(const edge &A, const edge &B){
    return A.w < B.w;
}

int edge_chosen_id[MAXN];

#define e e_qaq

int debug_val;/*最小生成树权*/
int calc(const int &n, const int &C){
    debug_val =0;

    tot =0;
    for(int i =0, j =0; i < totb || j < totw;){
        if(i < totb && j < totw){
            if(e_b[i].w <= e_w[j].w+C)/*优先黑边 -> 尽可能少选白边 ( -> 最小值区间左端点 )*/
                e[tot++] =e_b[i++];
            else
                e[tot] =e_w[j++], e[tot++].w +=C;
        }
        else if(i < totb)
            e[tot++] =e_b[i++];
        else
            e[tot] =e_w[j++], e[tot++].w +=C;
    }

    clear_disjointSet(n);
    int cnt =0, ret =0;
    for(int i =0; cnt < n-1 && i < tot; ++i)
        if(get_root(e[i].u) != get_root(e[i].v)){
            debug_val +=e[i].w;
            if(e[i].col == 0)
                ++ret;
            merge(e[i].u, e[i].v);
            edge_chosen_id[cnt] =e[i].id;
            ++cnt;
        }

    return ret;
}

#undef e

/*------------------------------Wrok------------------------------*/

bool check_illegal(const int &n, const int &k){/*构造生成树时尽可能地不选白边*/
    clear_disjointSet(n);
    int cnt =0, cnt_w =0;
    for(int i =0; i < totb && cnt < n-1; ++i)
        if(get_root(e_b[i].u) != get_root(e_b[i].v)){
            merge(e_b[i].u, e_b[i].v);
            ++cnt;
        }
    for(int i =0; i < totw && cnt < n-1; ++i)
        if(get_root(e_w[i].u) != get_root(e_w[i].v)){
            merge(e_w[i].u, e_w[i].v);
            ++cnt_w;
            ++cnt;
        }
    return (k < cnt_w || cnt != n-1);
}

edge e_backup[MAXM];
int tmp_backup, C_backup, debug_val_backup;

int cnt_l[MAXM], cnt_r[MAXM], tot_cnt;
bool e_chosen[MAXM];/*标记每种不同的边权中，选最少白边方案 ( 可能是多种方案中的一种 ) 中的白边*/

int e_ans[MAXN], tote_ans;

#define e e_backup

/*->>这里和 wqs 二分基本无关*/
/*解应当一定存在*/
void find_a_solution(const int &n, const int &m, const int &k){
    for(int i =0; i < m; ++i){
        if(i == 0){
            cnt_l[0] =0;
            ++tot_cnt;
        }
        else if(e[i].w != e[i-1].w){
            cnt_r[tot_cnt-1] =i-1;
            cnt_l[tot_cnt] =i;
            ++tot_cnt;
        }
        if(i == m-1)
            cnt_r[tot_cnt-1] =m-1;
    }

    /*找出一种最小生成树方案，使得白边最少*/
    clear_disjointSet(n);
    int cnt =0;
    for(int i =0; cnt < n-1; ++i){
        if(get_root(e[i].u) != get_root(e[i].v)){
            if(e[i].col == 0)
                e_chosen[i] =1;
            merge(e[i].u, e[i].v);
            ++cnt;
        }
        ++i;
    }

    clear_disjointSet(n);
    cnt =0;
    int delta_w =k-tmp_backup;/*还差多少白边*/
    for(int chunk =0; chunk < tot_cnt && cnt < n-1; ++chunk){/*注意只有同边权的边之间会 " 替换 " ( 影响 )*/
        for(int i =cnt_l[chunk]; i <= cnt_r[chunk]; ++i)/*先选 " 白边最少的方案 " 中的白边*/
            if(e_chosen[i]){
                merge(e[i].u, e[i].v);
                e_ans[tote_ans++] =e[i].id;
                ++cnt;
            }
        if(delta_w > 0)/*还需要多选一些白边*/
            for(int i =cnt_l[chunk]; delta_w > 0 && i <= cnt_r[chunk]; ++i)
                if(!e_chosen[i] && e[i].col == 0){
                    if(get_root(e[i].u) != get_root(e[i].v)){
                        merge(e[i].u, e[i].v);
                        e_ans[tote_ans++] =e[i].id;
                        --delta_w;
                        ++cnt;
                    }
                }
        for(int i =cnt_l[chunk]; i <= cnt_r[chunk]; ++i)/*最后选黑边*/
            if(e[i].col == 1){
                if(get_root(e[i].u) != get_root(e[i].v)){
                    merge(e[i].u, e[i].v);
                    e_ans[tote_ans++] =e[i].id;
                    ++cnt;
                }
            }
    }
}

#undef e

/*------------------------------Main------------------------------*/

int read(){
    int x =0; char c =getchar();
    while(c < '0' || c > '9') c =getchar();
    while(c >= '0' && c <= '9') x =(x<<1)+(x<<3)+(48^c), c =getchar();
    return x;
}

int main(){
    int n =read(), m =read(), k =read();
    for(int i =0; i < m; ++i){
        int s =read(), t =read(), c =read();
        if(s == 1 || t == 1){
            e_w[totw].u =s;
            e_w[totw].v =t;
            e_w[totw].w =c;
            e_w[totw].col =0;
            e_w[totw].id =i+1;
            ++totw;
        }
        else{
            e_b[totb].u =s;
            e_b[totb].v =t;
            e_b[totb].w =c;
            e_b[totb].col =1;
            e_b[totb].id =i+1;
            ++totb;
        }
    }
    sort(e_b, e_b+totb, cmp);
    sort(e_w, e_w+totw, cmp);

    /*检查 k 是否合法 ( 函数取值在 k 是否不存在 )*/
    if(k > n-1 || k > totw){/*上界检查 - 边不足*/
        puts("-1");
        return 0;
    }
    else if(check_illegal(n, k)){/*下界检查 - 最少可选的白边过多；以及顺便检查是否联通*/
        puts("-1");
        return 0;
    }

    int l =-5e8, r =5e8;
    while(l <= r){/*wqs*/
        int mid =(l+r)>>1;
        int tmp =calc(n, mid);
        if(tmp < k){
            debug_val_backup =debug_val;
            tmp_backup =tmp;
            C_backup =mid;
            for(int i =0; i < tot; ++i)
                e_backup[i] =e_qaq[i];
        }
        if(tmp < k)
            r =mid-1;
        else if(tmp > k)
            l =mid+1;
        else
            break;
    }

    if(l <= r){/*直接找到了答案*/
        printf("%d\n", n-1);
        for(int i =0; i < n-1; ++i)
            printf("%d ", edge_chosen_id[i]);
        return 0;
    }
    else{/*需要构造方案*/
        find_a_solution(n, m, k);
    //  printf("%d\n", debug_val_backup-C_backup*k);/*最小生成树权*/
        printf("%d\n", n-1);
        for(int j =0; j < n-1; ++j)
            printf("%d ", e_ans[j]);
    }
}

一些话

原本是打算好好证明下这种构造方式的正确性的...

结果写着写着发现与其写这么一大段还不如直接归约到 Kruskal 上...（当然也没写完，因为时间等等原因 \fad）

如果有人想继续探索这种构造方案的性质的话，这里就放几个之前写在正文的引理：

引理 1. 对于边权均不相等的无向图，其最小生成树唯一

证明只需考虑反证法即可（以下证明搬自维基）：

引理 2. 若无向图有多种最小生成树方案，则所有方案的每种边权的边数都是相等的

只需套用证明 引理 1. 的模式即可

引理 3. 在无向图的多种最小生成树方案之间，若一条边 e_1 能 “替换” 另一条同边权的边 e_2，那么它们一定同时在某个环上

（“替换” 这个词可能有点不严谨...这样写感觉比较简洁，见谅X）

证明很显然。否则 “替换” 后的方案就不再是生成树了

希望有所帮助X