Cod sursa(job #3373098)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 6 noiembrie 2026 08:46:44
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int nr, suma;
int t[200001];
int level[200001];
vector<pair<int,int>> ans;
struct muchie{
    int cost,x,y;
}muchii[400001];
bool cmp(muchie a,muchie b)
{
    return a.cost < b.cost;
}
int find(int x)
{
    if(t[x] == x)return x;
    return t[x] = find(t[x]);
}
void unire(int x,int y, int c)
{
    int rx = find(x);
    int ry = find(y);
    if(rx != ry)
    {
        nr++;
        ans.push_back({y,x});
        suma+=c;
        if(level[rx] > level[ry])
        {
            t[ry] = rx;
        }else{
            t[rx] = ry;
            if(level[rx] == level[ry])
                level[ry]++;
        }
    }
}
int main()
{
    int n,m; fin >> n >> m;
    for(int i = 1; i<=m;i++)
    {
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
    }
    sort(muchii + 1, muchii + m + 1, cmp);
    for(int i = 1 ;i<=n;i++)t[i] = i;
    for(int i = 1;i<=m;i++)
    {
        int cost = muchii[i].cost;
        int x = muchii[i].x;
        int y = muchii[i].y;
        unire(x,y,cost);
    }
    /*cout << '\n';
    for(int i = 1 ;i<=m;i++)
        cout << muchii[i].x << " " << muchii[i].y << " " << muchii[i].cost << '\n';*/
        fout << nr << '\n' << suma << '\n';
        for(auto i : ans){
            fout << i.first << " " << i.second << '\n';
        }

    return 0;
}