Cod sursa(job #3373205)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 6 noiembrie 2026 12:33:05
Problema Arbore partial de cost minim Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int parent[101], sz[101], n, m;
vector<pair<int, int>> sol;
struct muchi{
  int u, v, c;
};
muchi v[10001];
bool operator<(muchi a, muchi b){
  return a.c < b.c;
}
void init(){
   for(int i = 1;i<=n;i++){
    sz[i] = 1;
    parent[i] = i;
   }
}
int find(int x){
   if(parent[x] == x)
    return x;
   return parent[x] = find(parent[x]);
}
void union_sz(int a, int b){
   a = find(a);
   b = find(b);
   if(sz[a] < sz[b])
    swap(a, b);
   parent[b] = a;
   sz[a] += sz[b];
}
int main()
{

  fin >> n >> m;init();
  for(int i = 1;i<=m;i++)
    fin >> v[i].u >> v[i].v >> v[i].c;
  sort(v + 1, v + m + 1);
  int cost = 0, alese = 0;
  for(int k = 1;k<=m;k++)
  {
      int i = v[k].u;
      int j = v[k].v;
      if(find(i) != find(j)){
        cost+=v[k].c;
        union_sz(i, j);
        sol.push_back({i, j});
        alese++;
        if(alese == n - 1)break;
      }
  }
  fout << cost << endl << n - 1 << endl;
  for(auto i : sol)
    fout << i.first << " " << i.second << "\n";
           return 0;

}