Mai intai trebuie sa te autentifici.
Cod sursa(job #3373099)
| Utilizator | Data | 6 noiembrie 2026 08:47:44 | |
|---|---|---|---|
| Problema | Arbore partial de cost minim | Scor | 100 |
| 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 << suma << '\n' << nr << '\n';
for(auto i : ans){
fout << i.first << " " << i.second << '\n';
}
return 0;
}
