Submission

Score: 100

User: 12345678

Problemset: รัฐบาล

Language: cpp

Time: 0.003 second

Submitted On: 2025-11-18 10:34:31

#include <bits/stdc++.h>

using namespace std;

const int nx=105, ex=1e4+5;

int n, m, u, v, w, dsu[nx], mx[nx][nx], cst, sec=INT_MAX;
vector<tuple<int ,int, int>> edg, unused;
vector<pair<int ,int>> d[nx];

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

void fillmx(int u, int p, int rt, int curmx)
{
    mx[rt][u]=curmx;
    for (auto [v, w]:d[u]) if (v!=p) fillmx(v, u, rt, max(curmx, w));
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u>>v>>w, edg.push_back({w, u, v});
    for (int i=1; i<=n; i++) dsu[i]=i;
    sort(edg.begin(), edg.end());
    for (auto [w, u, v]:edg)
    {
        if (find(u)==find(v)) unused.push_back({w, u, v});
        else cst+=w, dsu[find(u)]=find(v), d[u].push_back({v, w}), d[v].push_back({u, w});
    }
    for (int i=1; i<=n; i++) fillmx(i, i, i, 0);
    for (auto [w, u, v]:unused) sec=min(sec, cst+w-mx[u][v]);
    cout<<cst<<' '<<sec;
}