Submission

[PPPPPP-SSS]

Score: 0

User: meme_boi2

Problemset: รัฐบาล

Language: cpp

Time: 0.008 second

Submitted On: 2025-04-19 19:33:32

#include <bits/stdc++.h>
using namespace std;
int n, m;
#define tii tuple <int,int,int> 
vector<int> pa(502);
int find(int i){
    if(pa[i] == i) return i;
    else return pa[i] = find(pa[i]); 
}
vector<tii> path;

void U(int u, int v){
    u = find(u); v = find(v); 
    if(u != v){
        if(u > v) pa[u] = v;
        else pa[v] = u;
    }
}
int solve(int skip){
    // priority_queue<tii,vector<tii>,greater<tii>> pq1;
    for(int i = 1; i <= n; i++) pa[i] = i; 
    int cnt = 0, ptr = 0, normal = 0;
    while(ptr < m){
   //     auto [w,u,v] = path[ptr];
        int w = get<0> (path[ptr]), u = get<1>(path[ptr]), v = get<2>(path[ptr]);
        if(ptr == skip) {
            ptr++;
            continue;
        }
        ptr++;
        if(find(u) != find(v)){
            U(u,v);
            cnt++;
            normal += w;
        }
        if(cnt == n-1) break;
    }
    return cnt == n-1 ? normal : INT_MAX;
}
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i<= n; i++) pa[i] = i;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        tuple <int,int,int> tup = make_tuple(w,u,v);
        path.push_back(tup);
    }
    sort(path.begin(),path.end());
    int nor = solve(INT_MAX), low = INT_MAX;
    for(int i = 0; i < m; i++){
        for(int j = 1; j <= n; j++) pa[j] = j; 
        low = min(low, solve(i) != nor ? solve(i) : INT_MAX);
    }
    cout << nor << ' ' << low;
}