Cod sursă (job #14503)

Utilizator avatar dushmi Mihai-Alexandru Dusmanu dushmi IP ascuns
Problemă Zapada (clasele 11 și 12) Compilator cpp | 2,62 kb
Rundă Concurs clasele 11-12 Status evaluat
Dată 8 mar. 2013 14:42:13 Scor 100
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct edge {
    int x, y, c;
};

const int kMaxN = 10005;

vector <edge> v, mst;

int oldC, N, M, K, dad[kMaxN], dim[kMaxN];

bool comp(const edge &A, const edge &B) {
    return (A.c < B.c);
}

inline int compress(int x) {
    if (dad[x] == 0)
        return x;

    return (dad[x] = compress(dad[x]));
}

int initial_mst() {
    for (int i = 1; i <= N; ++i)
        dad[i] = 0, dim[i] = 1;

    int C = 0;

    int rx, ry;

    for (size_t i = 0; i < v.size(); ++i) {
        rx = compress(v[i].x);
        ry = compress(v[i].y);

        if (rx != ry) {
            if (dim[rx] < dim[ry])
                dad[rx] = ry, dim[rx] += dim[ry];
            else
                dad[ry] = rx, dim[ry] += dim[rx];
            mst.push_back(v[i]);
            C += v[i].c;
        }
    }

    return C;
}

int update_mst(edge aux) {
    if (aux.c > mst[mst.size() - 1].c)
        return oldC;

    for (int i = 1; i <= N; ++i)
        dad[i] = 0, dim[i] = 1;

    int C = 0;

    int rx, ry;

    bool ok = 0;

    size_t pos1 = 0, pos2 = 0;

    for (size_t i = 0; i < mst.size(); ++i) {
        if (!ok && aux.c <= mst[i].c) {
            rx = compress(aux.x);
            ry = compress(aux.y);

            if (rx != ry) {
                if (dim[rx] < dim[ry])
                    dad[rx] = ry, dim[rx] += dim[ry];
                else
                    dad[ry] = rx, dim[ry] += dim[rx];
                C += aux.c;
                pos1 = i;
            } else
                return oldC;

            ok = 1;
        }

        rx = compress(mst[i].x);
        ry = compress(mst[i].y);

        if (rx != ry) {
            if (dim[rx] < dim[ry])
                dad[rx] = ry, dim[rx] += dim[ry];
            else
                dad[ry] = rx, dim[ry] += dim[rx];
            C += mst[i].c;
        } else
            pos2 = i;
    }

    for (size_t i = pos2; i > pos1; --i)
        swap(mst[i], mst[i - 1]);

    swap(mst[pos1], aux);

    return C;
}

int main() {
    freopen("zapada.in", "r", stdin);
    freopen("zapada.out", "w", stdout);

    scanf("%d%d%d", &N, &M, &K);

    for (int i = 1; i <= M; ++i) {
        edge aux;
        scanf("%d%d%d", &aux.x, &aux.y, &aux.c);
        v.push_back(aux);
    }

    sort(v.begin(), v.end(), comp);

    printf("%d\n", (oldC = initial_mst()));

    for (int i = 1; i <= K; ++i) {
        edge aux;
        scanf("%d%d%d", &aux.x, &aux.y, &aux.c);
        printf("%d\n", (oldC = update_mst(aux)));
    }

    return 0;
}