Cod sursă (job #18837)

Utilizator avatar mihai995 Andreescu Mihai mihai995 IP ascuns
Problemă Zapada (clasele 11 și 12) Compilator cpp | 2,13 kb
Rundă Arhiva de probleme Status evaluat
Dată 12 mai 2013 01:33:43 Scor 60
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 10001, M = 100001, inBuffSize = 1e6;

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, lastCost;
char inBuff[inBuffSize];
Pmd P;

ofstream out("zapada.out");

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

    edge[poz + 1] = A;
    ++nrE;

    return poz + 1;
}

int evalApm(int mustHave){
    int cost = 0, size = 0;

    P.init(n);
    for (int i = 1 ; i <= nrE ; i++)
        if (P.merge(edge[i].x, edge[i].y)){
            cost += edge[i].c;
            edge[++size] = edge[i];
        } else if (i == mustHave)
            return lastCost;

    nrE = n - 1;

    return lastCost = cost;
}

int main(){
    int times;
    Muchie A;

    FILE* in = fopen("zapada.in", "r");
    setvbuf(in, inBuff, _IOFBF, inBuffSize);

    fscanf(in, "%d %d %d", &n, &nrE, &times);

    for (int i = 1 ; i <= nrE ; i++)
        fscanf(in, "%d %d %d", &edge[i].x, &edge[i].y, &edge[i].c);

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

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

    while (times--){
        fscanf(in, "%d %d %d", &A.x, &A.y, &A.c);

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

    return 0;
}