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

· · 题解

对于“特别-普通”的小路进行标记，题目转化为至少包含 w 个被标记小路的 MST 是什么，这就是一个经典的 WQS 二分。

某个权值改变可以控制取数个数的，且结果有单调性的使用 WQS 二分。此题对于被标记小路加一个权值，然后跑 MST，权值大会少选被标记小路，权值小会多选被标记小路。

此题另一难点在于判断不可能的情况。如果到输出答案的时候按所选取的权值再跑一遍，（由于有一些边权一样的边答案是一个区间）答案区间中如果还没有包含要求个数那么就输出不可能。在一开始输入的时候判断一下给定的全选是否联通，不联通也输出不可能。

代码如下，实际上就是一个板子，连 DP 都不是。


#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int u,v,w,col;
}a[500005],b[500005];
int fa[200005];
int n,m,need;
    int min_ = 1e18;
int find(int x){return (x==fa[x]?x:fa[x] = find(fa[x]));}
bool cmp(node x, node y){
    if (x.w == y.w) return x.col > y.col;//优先选黑的
    return x.w< y.w;
}
bool cmp2(node x, node y){
    if (x.w == y.w) return x.col < y.col;//优先选白的
    return x.w< y.w;
}
void _init_(int x,int id){
    //初始化
    for (int i = 1; i <= n; i++)fa[i] = i;
    set<tuple<int,int,int>> vis;
    //加权
    for (int i = 1; i <= m; i++){
        b[i].u = a[i].u,b[i].v = a[i].v,b[i].col = a[i].col;
        if (!a[i].col) {
            b[i].w = a[i].w+x;
            vis.insert({b[i].u,b[i].v,b[i].w}),vis.insert({b[i].v,b[i].u,b[i].w});

        }//黑边全为正，所以白边为负的一定没有匹配(还有图是无向的)
        if (a[i].col) b[i].w = a[i].w;
    }
    if (id) sort(b+1,b+1+m, cmp);
    else  sort(b+1,b+1+m, cmp2);
}
int check(int x,int id){
    _init_(x,id);
    //跑MST
    int ans = 0,sum = 0;
    for (int i = 1; i <= m; i++){
        int px  = find(b[i].u),py  = find(b[i].v);
        if (px != py){
            fa[px] = py;
            sum += b[i].w;
            ans += (b[i].col==0);
        }
    }
    if (need >= ans) min_=sum-need*x;
    return ans;
}
bool num[200006];
signed main(){
    int k;
    ios::sync_with_stdio(0);
    cin.tie(0);
     cin >> n >> m >> k >> need;
    for (int i = 1; i <= k; i++){int x;cin >> x,num[x]=1;}
    for (int i = 1; i <= m; i++){
        cin >> a[i].u >> a[i].v >> a[i].w;
        if (num[a[i].u]^num[a[i].v]) a[i].col = 0;
        else a[i].col =1;
    }
    for (int i = 1; i <= n; i++)fa[i] = i;
    for (int i = 1; i <= m; i++){
        int px  = find(a[i].u), py  = find(a[i].v);
        if (px != py) fa[px] = py;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) cnt +=(fa[i] == i);
    if (cnt != 1) {cout <<-1;return 0;}
    int l = -100000,r = 100000,id = 0;
    while (l <= r){
        int mid = (l+r)/2;
        int tmp =check(mid,1);
        if (need < tmp) l = mid+1;
        if (need >= tmp) id = mid,r = mid-1;
    }
    int ansl = check(id,1),ansr = check(id,0);
    if (ansl <= need && ansr >= need)cout << min_;
    else cout << -1;
    return 0;
}