Submission

[-SSSSSSSSS][-SSSSSSSSSSSSSSSSSSS]

Score: 0

User: Nathlol2

Problemset: E.Kingdom

Language: cpp

Time: 0.083 second

Submitted On: 2025-03-04 16:05:02

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

const int N = 100000;

vector<pair<int, pair<int, int>>> g;
vector<vector<int>> ag;
int p[N];
vector<bool> vis(N, false);

int _find(int x){
    if(x == p[x]) {
        return x;
    }
    return p[x] = _find(p[x]);
}

void _union(int x, int y){
    int X = _find(x);
    int Y = _find(y);
    if(X != Y) p[X] = Y;
}

void dfs(int x){
    vis[x] = true;
    for(auto i : ag[x]){
        if (!vis[i]){
            dfs(i);
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;
    ag.assign(n, vector<int>());
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g.push_back({c, {a, b}});
        ag[a].push_back(b);
        ag[b].push_back(a);
    }
    sort(g.begin(), g.end(), [](const pair<int, pair<int, int>>& a, const pair<int, pair<int, int>>& b) {
    if (a.first != b.first) return a.first > b.first;
    if (a.second.first != b.second.first) return a.second.first > b.second.first;
    return a.second.second > b.second.second;
});

    for(int i = 0; i < n; i++){
        p[i] = i;
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            ans += k;
            dfs(i);
        }
    }
    ans -= k;
    for (auto [w, P] : g){
        auto [a, b] = P;
        if(_find(a) != _find(b)){
            _union(a, b);
            if (w < k){
                ans += k - w;
            }
        }else{
            ans += 1;
        }
    }
    cout << ans << '\n';
}