Solution Tree I

\(wqs\)二分

分析：设\(g(x)\)为恰好选\(x\)条白边的最小生成树权值和，那么经过我们可以证明出\(g\)是一个下凸函数（其实可以\(dp\)的……）

然后我们就可以用\(wqs\)二分了

这玩意儿通常用来解决有某种限制，每个物品有个权值，钦定必须选\(x\)个时候的最大/小权值和

要求函数\(g\)必须是凸函数，这样我们才可以对导函数进行二分

以上凸函数为例，我们要求的是\(g\)在给定的\(m\)处的取值，显然我们没法直接算出来（废话，不然干嘛不直接算，雾）

但是我们可以通过贪心 / \(dp\)等等来求出不考虑限制的时候的最大函数值，顺带求出自变量的值。然后我们看这个函数\(g\)的导函数\(g'\)，当\(g\)取到最大值的时候\(g'\)交\(x\)轴

如果我们把\(g(x)\)加上\(kx\)的话，不就等价于把导函数向上平移\(k\)个单位了吗

我们二分\(k\)，使得导函数交\(x\)轴于我们期望的\(m\)，然后这个时候我们就可以求出\(g(m)\)啦

完了？

我们加上了\(kx\)，也就是对\(g(m)\)加上了\(km\)，记得减掉

此题同理，我们二分一个\(k\)，对所有白边的权值加上\(k\)，跑\(Kruskal\)即可

黑白边同权选白边，然后没必要每次都做快排，可以黑白边分开然后每次跑归并排序，这样可以省下一个\(log\)的复杂度

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100;
inline int read(){
    int x = 0;char c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c))x = x * 10 + c - '0',c = getchar();
    return x;
}
struct Edge{
    int from,to,dist,col;
}Edges[maxn],black[maxn],white[maxn];
int f[maxn],n,m,need,sz,black_siz,white_siz;
inline void init(){
    for(int i = 1;i <= n;i++)f[i] = i;
    sz = n;
}
inline int find(int x){
    return (x == f[x]) ? x : f[x] = find(f[x]);
}
inline void merge(int a,int b){
    int x = find(a),y = find(b);
    if(x != y){
        sz--;
        f[x] = y;
    }
}
inline int kruskal(int delta){
    int res = 0,posa = 1,posb = 1,tot = 0;
    while(posa <= white_siz && posb <= black_siz)
        if(white[posa].dist + delta <= black[posb].dist)Edges[++tot] = white[posa++],Edges[tot].dist += delta;
        else Edges[++tot] = black[posb++];
    while(posa <= white_siz)Edges[++tot] = white[posa++],Edges[tot].dist += delta;;
    while(posb <= black_siz)Edges[++tot] = black[posb++];
    init();
    for(int i = 1;i <= m && sz != 1;i++){
        const Edge &e = Edges[i];
        if(find(e.from) != find(e.to))res += !e.col;
        merge(e.from,e.to);
    }
    return res;
}
int main(){
    n = read(),m = read(),need = read();
    for(int u,v,w,c,i = 1;i <= m;i++){
        u = read() + 1,v = read() + 1,w = read(),c = read();
        if(c == 0)white[++white_siz] = Edge{u,v,w,c};
        else black[++black_siz] = Edge{u,v,w,c};
    }
    sort(white + 1,white + 1 + white_siz,[](const Edge &a,const Edge &b){return a.dist < b.dist;});
    sort(black + 1,black + 1 + black_siz,[](const Edge &a,const Edge &b){return a.dist < b.dist;});
    int l = -111,r = 111,ans = 233;
    while(l <= r){
        int mid = (l + r) >> 1,tmp = kruskal(mid);
        if(tmp < need)r = mid - 1;
        else ans = mid,l = mid + 1;
    }
    if(ans == 233)abort();
    int posa = 1,posb = 1,tot = 0;
    while(posa <= white_siz && posb <= black_siz)
        if(white[posa].dist + ans <= black[posb].dist)Edges[++tot] = white[posa++],Edges[tot].dist += ans;
        else Edges[++tot] = black[posb++];
    while(posa <= white_siz)Edges[++tot] = white[posa++],Edges[tot].dist += ans;
    while(posb <= black_siz)Edges[++tot] = black[posb++];
    init();
    ans *= -need;
    for(int i = 1;i <= m && sz != 1;i++){
        const Edge &e = Edges[i];
        if(find(e.from) != find(e.to))ans += e.dist;
        merge(e.from,e.to);
    }
    printf("%d\n",ans);
    return 0;
}

我们

题解 P2619 【[国家集训队2]Tree I】

Solution Tree I