Submission

Score: 0

User: theem1502

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-18 21:03:37

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

bool comp(pair<pair<int,int>,int> a, pair<pair<int,int>, int> b) {
    if (a.second > b.second) {
        return false;

    }
    return true;
}

int findroot(int num,vector<int> &parent) {
    if (num == parent[num]) {
    return num;
    }
    return parent[num] = findroot(parent[num], parent);
}

int main() {
    int v, e;
    cin >> v >> e;
    vector<pair<pair<int,int>,int>> arr(e);
    //vector<int> costarr(e);
    for (int i = 0 ; i < e; i++) {
        cin >> arr[i].first.first >> arr[i].first.second >> arr[i].second;
        arr[i].first.first--; arr[i].first.second--;

    }

    vector<vector<bool>> mapping(v, vector<bool> (v, false));
    vector<pair<int,int>> marked;
    int cost = 0;
    vector<int> parent(v);
    for (int i = 0; i < v; i++) {
        parent[i] = i;
    }

    sort(arr.begin(), arr.end(), comp);

    for (int i = 0; i < e; i++) {
        int a = findroot(arr[i].first.first, parent), b = findroot(arr[i].first.second, parent);
        if (a == b) {
            continue;
        }
        parent[a] = b;
        marked.push_back(make_pair(a,b));
        cost += arr[i].second;
    }


   // cout << "cost = " << cost << "\n";
    int mincost = 1e9;
    for (int k = 0; k < v-1; k++) {
        mapping[marked[k].first][marked[k].second] = true;
                for (int i = 0; i < v; i++) {
        parent[i] = i;
    }
            int newcost = 0;
            for (int i = 0; i < e; i++) {
            if (mapping[arr[i].first.first][arr[i].first.second] == true) {
                continue;
            }

        int a = findroot(arr[i].first.first, parent), b = findroot(arr[i].first.second, parent);
        if (a == b) {
            continue;
        }
        parent[a] = b;
        marked.push_back(make_pair(a,b));
        newcost += arr[i].second;
    }

    if (newcost < mincost) {
        mincost = newcost;
    }





        mapping[marked[k].first][marked[k].second] = false;
    }
    cout << cost << " " << mincost;


}