Cod sursa(job #2027018)

Utilizator osiaccrCristian Osiac osiaccr Data 25 septembrie 2017 14:48:56
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct elem {
    int x, y, cost;
} v[400001];

int n, m, T[100001];

int cpm (const elem a, const elem b) {
    return a.cost >= b.cost;
}

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }

    sort (v + 1, v + m + 1, cmp);

    for (int i = 1; i <= n; i++) {
        T[i] = -1;
    }

    for (int i = 1; i <= m; i++) {
        int rx, int ry;
        rx = rad (v[i].x);
        ry = rad (v[i].y);
        if (rx != ry) {
            if (T[rx] < T[ry]) {
                T[rx] += T[ry];
                T[ry] = rx;
            }
            else {
                T[ry] += T[rx];
                T[rx] = ry;
            }
        }
    }

    return 0;
}