Submission

[PPPPPP-SSS]

Score: 0

User: meme_boi2

Problemset: รัฐบาล

Language: cpp

Time: 0.013 second

Submitted On: 2025-04-19 21:15:12

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define pii pair<int,int>
#define tii tuple<int,int,int>
//priority_queue<tii,vector<tii>,greater<tii>> pq;
bool comp(tii a, tii b){
    return get<2>(a) < get<2> (b);
}
vector<int> pa(102);
int n, m;
int find(int i){
    if(pa[i] == i) return i;
    else return pa[i] = find(pa[i]);
}
void U(int u,int v){
    u = find(u), v = find(v);
    if(u > v) pa[v] = u;
    else pa[u] = v;
}
int calculate_MST(int X,vector<tii> path){
    for(int i = 1; i <= n; i++) pa[i] = i;
    int cut = 0, idx = 0, MisterO = 0;
    while(cut != n-1 && idx < m){
        auto [u,v,w] = path[idx];
        idx++;
        if(idx-1 == X) continue;
        if(find(u) != find(v)){
            cut++;
            U(u,v);
            MisterO+=w;
        }
    }
    return cut == n-1 ? MisterO : 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;
    vector<tii> path(m);
    for(int i = 0; i < m; i++){
        int u,v ,w;
        cin >> u >> v >> w;
        path[i] = {u,v,w};
    }
    sort(path.begin(),path.end(),comp);
    int cut = 0, idx = 0, MisterO = 0;
    while(cut != n-1 && idx < m){
        auto [u,v,w] = path[idx];
        idx++;
        if(find(u) != find(v)){
            cut++;
            U(u,v);
            MisterO+=w;
        }
    }
    int njoop = INT_MAX;
    for(int i = 0; i < m; i++){
        int DevJ = calculate_MST(i,path);
        if(DevJ < njoop && DevJ != MisterO) njoop = DevJ;
    }
    cout << MisterO << ' ' << njoop;
}