提交记录

代码：

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

typedef long long LL;
typedef pair<int, LL> PII;
const int N = 5e4 + 10, M = 5e5 + 10;

struct edge{
    int u, v, w, type;
    bool operator < (const edge x) const {
        if(w != x.w) return w < x.w;
        return type < x.type;
    }
}e[M];

int pa[N];
int n, m, st, k;

int find(int x)
{
    if(pa[x] == -1) return x;
    return pa[x] = find(pa[x]);
}

PII check()
{
    int Tcnt = 0, Dcnt = 0;
    LL sum = 0;
    for(int i=0; i < m; i ++ ){
        int u = find(e[i].u), v = find(e[i].v);
        if(u != v){
            pa[u] = v;
            sum += e[i].w;
            Tcnt ++ ;
            if(e[i].type == 0) Dcnt ++ ;
        }
    }
    if(Tcnt != n - 1) return {LONG_LONG_MAX, -1};
    return {Dcnt, sum};
}

LL get_ans()
{
    int cnt = 0;
    for(int i=0; i < m; i ++ ) if(e[i].type == 0) cnt ++ ;
    if(cnt < k) return -1; // 判断度是否大于等于k

    int l = -4e4, r = 4e4;
    LL ans = -1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        for(int i=0; i < m; i ++ )
            if(e[i].type == 0) e[i].w += mid;
        
        memset(pa, -1, sizeof pa);
        sort(e, e + m);
        
        PII pos = check();

        if(pos.first == LONG_LONG_MAX) return -1; // 判断是否联通

        if(pos.first >= k){
            l = mid;
            ans = pos.second - mid * k;
        }else r = mid - 1;

        for(int i=0; i < m; i ++ )
            if(e[i].type == 0) e[i].w -= mid;
    }

    return ans;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &st, &k);

    for(int i=0; i < m; i ++ ){
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        e[i] = {a, b, c};
        if(a == st || b == st) e[i].type = 0;
        else e[i].type = 1;
    }

    LL t = get_ans();

    if(t == -1) printf("Impossible");
    else printf("%lld", t);

    system("pause");
    return 0;
}