Submission

Score: 100

User: Chawin

Problemset: รัฐบาล

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-22 18:46:34

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

vector<int> pa;

int find(int n){
    if(n == pa[n]) return n;
    return pa[n] = find(pa[n]);
}

int dfs(int u, int target, int mx, vector<vector<pair<int,int>>> &adj, vector<bool> &visited){
    if(u == target) return mx;

    visited[u] = true;

    for(auto &x : adj[u]){
        int v = x.first;
        int w = x.second;
        if(!visited[v]){
            int res = dfs(v, target, max(mx, w), adj, visited);
            if(res != -1) return res;
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    pa.resize(n+1);
    for(int i = 0; i <= n; i++) pa[i] = i;

    vector<array<int, 3>> edges;
    for(int i = 0; i < m; i++){
        int x, y, c;
        cin >> x >> y >> c;

        edges.push_back({c, x, y});
    }

    sort(edges.begin(), edges.end());

    vector<bool> used(m, false);
    vector<vector<pair<int, int>>> adj(n+1);

    int D1 = 0;
    for(int i = 0; i < m; i++){
        int a = edges[i][1];
        int b = edges[i][2];

        int A = find(a);
        int B = find(b);

        if(A != B){
            pa[A] = B;
            D1 += edges[i][0];

            used[i] = true;

            adj[a].push_back({b, edges[i][0]});
            adj[b].push_back({a, edges[i][0]});
        }
    }

    int D2 = 1e9+7;
    for(int i = 0; i < m; i++){
        if(!used[i]){
            int c = edges[i][0];
            int a = edges[i][1];
            int b = edges[i][2];

            vector<bool> visited(n+1, false);
            int mx = dfs(a, b, 0, adj, visited);

            int nd = D1 + c - mx;

            if(nd >= D1){
                D2 = min(D2, nd);
            }
        }
    }

    cout << D1 << " " << D2;

    return 0;
}