题解：P16146 [ICPC 2017 NAIPC] Blazing New Trails

· · 题解

题意简述

在带权无向图中选出一棵生成树。部分顶点为特殊点。要求生成树中恰有 w 条边连接特殊点与普通点，并最小化总边权。若不存在则输出 -1。

解题思路

称连接两类顶点的边为异类边。给每条异类边的边权增加整数 x，其余边权不变，再求新边权下的最小生成树。记一棵树的原权值为 c，异类边数为 t，则修改后的权值为 c+xt。

随着 x 增大，使用异类边的代价增大，最小生成树中的异类边数单调不增。因此可以二分 x。

固定 x 时，最小生成树可能不唯一。Kruskal 算法遇到相同新边权时，优先处理异类边，可以最大化异类边数。优先处理普通边，则可以最小化异类边数。最小生成树之间可以通过等权边交换相互转化。交换一次只会让异类边数改变 0 或 1。因此，这两个极值之间的每个整数都能由某棵最小生成树达到。

固定某个 x。若最少异类边数不超过 w，最多异类边数又不少于 w，就能达到目标。此时存在一棵恰有 w 条异类边的最小生成树。设修改后的最小权值为 g(x)，则答案为：

g(x)-wx

边权均为整数。按异类边数限制得到的最优值具有离散凸性，所以相邻限制的分界斜率也是整数。只要目标异类边数可行，必能在某个整数 x 处落入上述区间。

原边权位于 [1,10^5]。取 x=-10^5 时，所有异类边都严格排在普通边前面。这样可以求出任意生成树中的最大异类边数。取 x=10^5 时则能求出最小异类边数，由此先判断可行性。

不必在每次二分中重新排序全部边。分别按原边权排序普通边和异类边。增加 x 不改变异类边内部的顺序。运行 Kruskal 时合并两个有序序列即可。预处理时间复杂度为 O(m\log m)。每次检查的时间复杂度为 O(m\alpha(n))。总时间复杂度为 O(m\log m+m\alpha(n)\log C)，空间复杂度为 O(n+m)，其中 C 为边权范围。

正确性证明

对于固定 x，Kruskal 算法按修改后的边权选边，所得树的修改后权值最小。相同权值内优先异类边，相当于在所有最小生成树中再次最大化异类边数；反向处理则最小化该数量。因此，算法计算的两个数量确为当前最小生成树集合的上下界。

若 w 位于这两个数量之间，等权边交换性质保证目标数量可以达到。存在一棵修改后权值为 g(x)、异类边数恰为 w 的树。它的原权值为 g(x)-wx。任意恰有 w 条异类边的树，修改后权值都不小于 g(x)。所以其原权值也不小于 g(x)-wx，此时得到的答案最优。

二分始终保留可能使 w 落入区间的方向。异类边数过少时减小 x，过多时增大 x。可行性检查和整数分界性质保证二分能找到所需的 x。若目标不在所有生成树可达到的数量区间内，则确实不存在合法方案。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<ll,int>;
const int N=200005;
const int M=500005;
struct Edge
{
    int u,v,w;
}e[2][M];
int n,cnt[2],fa[N],siz[N];
bool sp[N];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
pii mst(int x,bool op)
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        siz[i]=1;
    }
    int p[2]={},num=0,res=0;
    ll sum=0;
    while(num<n-1&&(p[0]<cnt[0]||p[1]<cnt[1]))
    {
        bool t;
        if(p[0]==cnt[0])t=1;
        else if(p[1]==cnt[1])t=0;
        else
        {
            int a=e[0][p[0]].w,b=e[1][p[1]].w+x;
            t=op?b<=a:b<a;
        }
        Edge a=e[t][p[t]++];
        int u=find(a.u),v=find(a.v);
        if(u==v)continue;
        if(siz[u]>siz[v])swap(u,v);
        fa[u]=v;
        siz[v]+=siz[u];
        num++;
        res+=t;
        sum+=a.w+t*x;
    }
    return num==n-1?pii(sum,res):pii(0,-1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,k,w;
    cin>>n>>m>>k>>w;
    for(int i=0;i<k;i++)
    {
        int x;
        cin>>x;
        sp[x]=1;
    }
    for(int i=0;i<m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        bool t=sp[u]!=sp[v];
        e[t][cnt[t]++]={u,v,c};
    }
    for(int i=0;i<2;i++)sort(e[i],e[i]+cnt[i],[](const Edge &a,const Edge &b){return a.w<b.w;});
    pii mx=mst(-100000,1),mn=mst(100000,0);
    if(mx.second<0||mn.second>w||mx.second<w)
    {
        cout<<-1<<'\n';
        return 0;
    }
    int l=-100000,r=100001;
    while(l<r)
    {
        int x=(l+r)>>1;
        mx=mst(x,1);
        mn=mst(x,0);
        if(mn.second<=w&&w<=mx.second)
        {
            cout<<mx.first-(ll)w*x<<'\n';
            return 0;
        }
        if(mx.second<w)r=x;
        else l=x+1;
    }
    return 0;
}