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

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

题意：

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

题目保证有解。

对于 100 % 100% 100% 的数据， n ≤ 5 × 1 0 4 , m ≤ 1 0 5 nleq 5times10^4,mleq 10^5 n≤5×104,m≤105。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

时间复杂度 O ( n log ⁡ n log ⁡ 222 ) O(nlog nlog 222) O(nlognlog222)

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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
        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
        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;
}

转载请说明出处