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

题目链接：P2619 [国家集训队]Tree I

题意：

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

题目保证有解。

对于 \(100\%\) 的数据，\(n\leq 5\times10^4,m\leq 10^5\)。

所有数据边权为 \([1,100]\) 中的正整数。

直接 \(O(nm)\) 的dp肯定是不行的，考虑wqs二分。

在这题中，wqs二分做的其实就是给白边增加额外权值

使最优方案恰好选满 \(\text{need}\) 条白边 。

假设二分的权值为 \(\text{mid}\) ，

若选了大于 \(\text{need}\) 条白边，则将白边边权增大，反之同理。

具体的，设选 \(x\) 条白边的最小花费 \(f(x)\)

注意到点集 \((x,f(x))\) 形成一个下凸壳

也就是 \(f(x)\) 为一个整数域的下凸函数

我们二分一个斜率 \(k\) ，用这条直线去尝试切凸壳

显然这条直线在不确定 \(y\) 轴截距时可以与这个凸壳有很多交点，

由斜截式方程得 \(y\) 轴截距公式为 \[ b=y-kx \] 代入得 \[ b(x)=f(x)-kx \] 而 \(b(x)\) 就是所有白边的边权减去 \(k\) 以后选 \(x\) 条白边的最小花费（最小生成树）

然后不考虑 \(x\) 的限制跑一遍kruskal求出一个修改后的最优解，

根据这个最优解（也就是最小的 \(b(x)\) ）对应的 \(x\) 改变左右端点

因为边权在 \([1,100]\) 间，所以设个 \(l=-111,r=111\) 即可

时间复杂度 \(O(n\log n\log 222)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

struct Edge
{
    int u,v,w,c;
}e[N];
int n,m,need,cnt,sum,u[N],v[N],w[N],c[N],f[N];
void init(){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){f[find(u)]=find(v);}
void kruskal(int mid)
{
    cnt=sum=0;  init();
    for(int i=1; i<=m; i++)
        if(c[i])e[i]={u[i],v[i],w[i],c[i]};
        else e[i]={u[i],v[i],w[i]-mid,c[i]};
    sort(e+1,e+1+m,[](Edge a,Edge b)
    {
        return a.w==b.w?a.c<b.c:a.w<b.w;
    });
    int tmp=0;
    for(int i=1; i<=m&&tmp<n; i++)
    {
        if(find(e[i].u)!=find(e[i].v))
        {
            merge(e[i].u,e[i].v);
            ++tmp; cnt+=(e[i].c^1);
            sum+=e[i].w;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> need;
    for(int i=1; i<=m; i++)
    {
        cin >> u[i] >> v[i] >> w[i] >> c[i];
        u[i]++; v[i]++;
    }
    int l=-111,r=111,ans=0;
    while(l<r)
    {
        int mid=(l+r)>>1;
        kruskal(mid);
        if(cnt>=need)
        {
            r=mid;
            ans=sum+need*mid;
        }else l=mid+1;
    }
    cout << ans << '\n';
    return 0;
}