Pagini recente » Cod sursa (job #2823261) | Cod sursa (job #455721) | Cod sursa (job #2668541) | Cod sursa (job #2822005) | Cod sursa (job #2278875)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
FILE*in = fopen("apm.in", "r");
FILE*out = fopen("apm.out", "w");
int T[200002];
vector<int> v[200002];
bool seen[200002];
int find_daddy(int x)
{
if(x!=T[x])
T[x]=find_daddy(T[x]);
return T[x];
}
void join(int x, int y)
{
int t1=find_daddy(x);
int t2 = find_daddy(y);
T[t2]=t1;
}
struct muchie
{
int nod1;
int nod2;
int cost;
};
muchie muc[400001];
bool cmp(muchie a, muchie b)
{
if(a.cost < b.cost)
return 1;
return 0;
}
int main()
{
int n, m, c, x, y, cost = 0, nrm = 0;
fscanf(in, "%d %d", &n, &m);
for(int i = 1; i<=n; i++)
{
T[i]=i;
}
for(int i = 1; i<=m; i++)
{
fscanf(in, "%d %d %d", &x, &y, &c);
muc[i].nod1 = x;
muc[i].nod2 = y;
muc[i].cost = c;
}
sort(muc+1, muc+m+1, cmp);
int i = 1;
while(nrm!=n-1)
{
int nod1, nod2;
nod1 = muc[i].nod1;
nod2 = muc[i].nod2;
if(find_daddy(nod1) != find_daddy(nod2))
{
join(nod1, nod2);
v[nod1].push_back(nod2);
v[nod2].push_back(nod1);
cost+=muc[i].cost;
nrm++;
}
i++;
}
fprintf(out, "%d\n", cost);
fprintf(out, "%d\n", n-1);
for(int i = 0; i<n; i++)
{
for(int j = 0; j<v[i].size();j++)
if(i<v[i][j])
fprintf(out, "%d %d\n", i, v[i][j]);
}
fclose(in);
fclose(out);
return 0;
}