# Cod sursa(job #1538530)

Utilizator Data 29 noiembrie 2015 12:21:35 Arbore partial de cost minim 100 cpp done Arhiva educationala 1.68 kb
``````#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>

using namespace std;

struct ARB{
int a, b, cost;
};

const int mmax = 400002;
const int nmax = 200002;

ARB arb[mmax];
int ind[mmax], n, m, md[nmax] , res[nmax];

bool mysort(const int &a, const int &b) { return arb[a].cost < arb[b].cost; };
void unire(int a, int b);
bool sameGroup(int a, int b);

int main(){
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
scanf("%d %d", &n, &m);

memset(arb, 0, (m+2) * sizeof(struct ARB));

for (int i = 0; i < m; i++) {
scanf("%d %d %d", &arb[i].a, &arb[i].b, &arb[i].cost);
ind[i] = i;
}

memset(md, 0, 4 * n + 8);
sort(ind + 1, ind + m + 1, mysort);

int k = 0,sum = 0;
for (int i = 1; i <= m; i++) {
if ( !sameGroup( arb[ind[i]].a, arb[ind[i]].b ) ) {
//add edge + join grups + update TotalCost
res[k++] = ind[i];
unire(arb[ind[i]].a, arb[ind[i]].b);
sum += arb[ind[i]].cost;
}
}

printf("%d\n%d\n", sum, n - 1);
for (int i = 0; i < k; i++)
printf("%d %d\n", arb[res[i]].a, arb[res[i]].b);
fclose(stdin);
fclose(stdout);
return 0;
}

void unire(int a, int b) {
int ha = 0, hb = 0, aa = a, bb = b;
while (md[aa] != 0) { aa = md[aa]; ha++; };
while (md[bb] != 0) { bb = md[bb]; hb++; };

int root;
if (ha > hb)	{ root = aa;	md[bb] = root; }
else			{ root = bb;	md[aa] = root; };

int tmp;
aa = a; bb = b;
while (aa != root)  { tmp = md[aa]; md[aa] = root; aa = tmp; };
while (bb != root)  { tmp = md[bb]; md[bb] = root; bb = tmp; };
}

bool sameGroup(int aa, int bb) {
while (md[aa] != 0)  aa = md[aa];
while (md[bb] != 0)  bb = md[bb];
return aa == bb;
}``````