Submission

Score: 100

User: KantaponZ

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2025-08-24 23:42:07

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

#define ll long long

struct Data {
    int u, v, w;
    bool operator<(const Data &o) const {
        if (w != o.w) return w < o.w;
        if (u != o.u) return u < o.u;
        return v < o.v;
    }
};

int N, M;
vector<Data> Edge;
vector<int> used;
int pa[105];
int ans1, ans2 = 1e9;

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

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        Edge.push_back({u, v, w});
    }

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

    // find the shortest cost
    for (int i = 1; i <= N; i++) pa[i] = i;
    for (int i = 0; i < Edge.size(); i++) {
        auto [u, v, w] = Edge[i];
        int pu = fp(u), pv = fp(v);
        if (pu == pv) continue;
        pa[pu] = pv;
        used.emplace_back(i);
        ans1 += w;
    }

    //find the second
    for (int i = 0; i < used.size(); i++) {
        int ct = 0, temp = 0;
        for (int i = 1; i <= N; i++) pa[i] = i;
        for (int j = 0; j < Edge.size(); j++) {
            if (used[i] == j) continue;
            auto [u, v, w] = Edge[j];
            int pu = fp(u), pv = fp(v);
            if (pu == pv) continue;
            pa[pu] = pv;
            temp += w;
            ct++;
        }
        if (ct == N - 1 && temp >= ans1) {
            ans2 = min(ans2, temp);
        }
    }

    cout << ans1 << " " << ans2;

}