Submission

Score: 100

User: Gump2011

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-08 17:31:00

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

int parent[105];

// Union-Find
int find(int x){
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

// Compare function สำหรับ sort
bool cmp(const array<int,3> &a, const array<int,3> &b){
    return a[2] < b[2]; // sort ตาม weight
}

// Kruskal
int kruskal(int n, vector<array<int,3>> &edges, vector<int> &mst_edges){
    for(int i=1;i<=n;i++) parent[i] = i;
    sort(edges.begin(), edges.end(), cmp); // ใช้ compare function ธรรมดา

    int cost = 0;
    mst_edges.clear();
    for(int i=0;i<edges.size();i++){
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        int pu = find(u), pv = find(v);
        if(pu != pv){
            parent[pu] = pv;
            cost += w;
            mst_edges.push_back(i);
        }
    }
    if(mst_edges.size() != n-1) return INT_MAX;
    return cost;
}

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

    int n,m;
    cin >> n >> m;
    vector<array<int,3>> edges(m);
    for(int i=0;i<m;i++){
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }

    vector<int> mst_edges;
    int D1 = kruskal(n, edges, mst_edges);

    int D2 = INT_MAX;
    for(int i=0;i<mst_edges.size();i++){
        for(int j=1;j<=n;j++) parent[j] = j;
        int cost = 0, count = 0;
        for(int k=0;k<edges.size();k++){
            if(k == mst_edges[i]) continue;
            int u = edges[k][0], v = edges[k][1], w = edges[k][2];
            int pu = find(u), pv = find(v);
            if(pu != pv){
                parent[pu] = pv;
                cost += w;
                count++;
            }
        }
        if(count == n-1) D2 = min(D2, cost);
    }

    cout << D1 << " " << D2 << "\n";
    return 0;
}