Submission

Score: 100

User: Bestzu

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-13 21:31:19

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

const int N = 110;
int parent[N];
int sz[N];
int n, m;
vector<int> ID[N][N];

void set_parent() {
    for(int i = 1; i <= n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

struct Edge {
    int w, u, v;
    bool operator<(const Edge &o) const {
        return w < o.w;
    }
};

int findhead(int u) {
    if(parent[u] == u) return u;
    return parent[u] = findhead(parent[u]);
}

void unite(int a, int b) {
    int heada = findhead(a);
    int headb = findhead(b);
    if(heada == headb) return;

    if(sz[heada] < sz[headb]) swap(heada, headb);

    sz[heada] += sz[headb];
    parent[headb] = heada;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    vector<Edge> edge;
    for(int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        edge.push_back({w, u, v});
        ID[u][v].push_back(i);
        ID[v][u].push_back(i);
    }
    set_parent();
    sort(edge.begin(), edge.end());

    int ans1 = 0;
    int cnt = 0;
    vector<int> used_edge_idx;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        tie(u, v, w) = tie(edge[i].u, edge[i].v, edge[i].w);
        if(findhead(u) != findhead(v)) {
            ans1 += w;
            used_edge_idx.push_back(i);
            unite(u, v);
            cnt++;
        }
        if(cnt == n-1) break;
    }
    int ans2 = INT_MAX;
    for(auto skip_idx : used_edge_idx) {
        set_parent();
        cnt = 0;
        int cur = 0;
        for(int i = 0; i < m; i++) {
            if(i == skip_idx) continue;
            int u, v, w;
            tie(u, v, w) = tie(edge[i].u, edge[i].v, edge[i].w);
            if(findhead(u) != findhead(v)) {
                cur += w;
                unite(u, v);
                cnt++;
            }
            if(cnt == n-1) {
                ans2 = min(cur, ans2);
                break;
            }
        }
    }
    cout << ans1 << " " << ans2;
    return 0;
}