Cod sursă (job #18834)

Utilizator avatar mihai995 Andreescu Mihai mihai995 IP ascuns
Problemă Zapada (clasele 11 și 12) Compilator cpp | 1,78 kb
Rundă Arhiva de probleme Status evaluat
Dată 12 mai 2013 00:50:19 Scor 40
#include <fstream>
#include <algorithm>
using namespace std;

const int N = 10001, M = 100001;

class Pmd{
    int T[N], D[N];

public:
    void init(int n){
        for (int i = 1 ; i <= n ; i++){
            T[i] = i;
            D[i] = 1;
        }
    }

    int tata(int x){
        if (T[x] == x)
            return x;

        return T[x] = tata(T[x]);
    }

    bool merge(int x, int y){
        x = tata(x);
        y = tata(y);

        if (x == y)
            return false;

        if (D[x] < D[y]){
            T[x] = y;
            D[y] += D[x];
        } else {
            T[y] = x;
            D[x] += D[y];
        }

        return true;
    }
};

struct Muchie{
    int x, y, c;

    Muchie(){
        x = y = c = 0;
    }

    Muchie(int _x, int _y, int _c){
        x = _x;
        y = _y;
        c = _c;
    }

    inline bool operator<(const Muchie& M) const {
        return c < M.c;
    }
};

Muchie edge[M];
int n, nrE, cost;
Pmd P;

ifstream in("zapada.in");
ofstream out("zapada.out");

void add(Muchie A){
    int poz;
    for (poz = nrE ; poz && edge[poz].c > A.c ; poz--)
        edge[poz + 1] = edge[poz];

    edge[poz + 1] = A;
}

int evalApm(){
    int cost = 0;

    P.init(n);
    for (int i = 1 ; i <= nrE ; i++)
        if (P.merge(edge[i].x, edge[i].y))
            cost += edge[i].c;

    return cost;
}

int main(){
    int times;
    Muchie A;

    in >> n >> nrE >> times;

    for (int i = 1 ; i <= nrE ; i++)
        in >> edge[i].x >> edge[i].y >> edge[i].c;

    sort(edge + 1, edge + nrE + 1);

    out << evalApm() << "\n";

    while (times--){
        in >> A.x >> A.y >> A.c;
        add(A);

        out << evalApm() << "\n";
    }

    return 0;
}