wqs二分。。。真乃神人也

· · 算法·理论

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

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 d 条白色边的生成树。

已知（玄学，蒙吧）：设d == i时答案为g(i)，则所有(i,g(i))构成的图像为一个凸包。

然后二分切线斜率k。

此时的b是把所有白边的权-=k之后跑一遍Kruskal模板得到的结果。

同时，i就是Kruskal最小生成树中白边的数量。

由此，可以得到g(i) = ki +b，即求出了(i,g(i))的结果。

然后，如果i == d，直接结束；

否则根据i与d的关系改变斜率（d在i左边就减小斜率，d在i右边就增大斜率）。

然后就可以最后求出(d,g(d))啦！时间复杂度O(emm我不知道)

我的代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define int long long
int V,E,d;
struct edge{
    int u,v,w;
    bool col;
}e[N];
int k,b;
bool cmp(edge A,edge B)
{
    if (A.w - k * (!A.col) == B.w - k * (!B.col)) return A.col < B.col;//这里！！！添加了边权相等优先选白边的政策
    return A.w - k * (!A.col) < B.w - k * (!B.col);
}
int g(int x)
{
    return k * x + b;
}
//并查集↓ 
int fa[N];
void init(){
    for (int i = 0;i <= V;i++)
    {
        fa[i] = i;
    }
}
int gets(int x)
{
    if (fa[x] == x) return x;
    return fa[x] = gets(fa[x]);
}
void merge(int x,int y)
{
    int fx = gets(x),fy = gets(y);
    if (fx != fy) fa[fy] = fx;
}
//并查集↑ 
struct xOy{
    int x,y;
};
xOy Kruskal(int mid)
{
    int cnt = 0,sum = 0,whitecnt = 0;
    sort(e+1,e+E+1,cmp);
    init();
    for (int i = 1;i <= E;i++)
    {
        if (cnt == V-1) break;
        int u = e[i].u,v = e[i].v,w = e[i].w,col = e[i].col;
        if (gets(u) != gets(v))
        {
            merge(u,v);
            cnt++;
            sum += w - k*(!col);
            if (!col) whitecnt++;
        }
    }
    return (xOy){whitecnt,sum};
}
signed main()//王钦石二分 直接拿下 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>V>>E>>d;
    int s,t,c;
    bool col;
    for (int i = 1;i <= E;i++)
    {
        cin>>s>>t>>c>>col;
        e[i] = {s,t,c,col};
    }
    int l = -105,r = 105,mid,i,b,ans;
    while (l <= r)
    {
        mid = (l + r) / 2;
        k = mid;//将斜率k设为mid
        xOy chk = Kruskal(mid);
        i = chk.x;
        b = chk.y;
        if (d <= i)
        {
            ans = b + k*d;//统计答案时手动加上kd
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout<<ans;
    return 0;
}