Cod sursă (job #271703)

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>

using namespace std;

FILE *f = fopen("zapada.in", "r");
FILE *g = fopen("zapada.out", "w");

const int BUF_SIZE = 4096;
const int NMAX = 11005;
const int MMAX = 100005;

struct edge
{
    int src, dest, wt;
};

char buf[BUF_SIZE];
int pos = BUF_SIZE;
int n, m, k;
edge A[MMAX];
int H[NMAX], F[NMAX];
edge V[MMAX];
int sum;

inline char getChar()
{
    if (pos == BUF_SIZE)
        {
         fread(buf, 1, BUF_SIZE, f);
         pos = 0;
        }
    return buf[pos ++];
}

inline int readInt()
{
    int result = 0;
    char c;
    do
        {
         c = getChar();
        }
    while (!isdigit(c));
    do
        {
         result = 10 * result + c - '0';
         c = getChar();
        }
    while (isdigit(c));
    return result;
}

void read()
{
    n = readInt();
    m = readInt();
    k = readInt();
    for (int i = 1; i <= m; ++ i)
        {
         A[i].src = readInt();
         A[i].dest = readInt();
         A[i].wt = readInt();
        }
}

inline bool cmp(edge A, edge B)
{
    if (A.wt < B.wt)
        return true;
    return false;
}

int root(int v)
{
    while (F[v])
        v = F[v];
    return v;
}

void unite(int x, int y)
{
    if (H[x] > H[y])
        F[y] = x;
    else
        {
         F[x] = y;
         if (H[x] == H[y])
            ++ H[y];
        }
}

void kruskal()
{
    memset(H, 1, sizeof(H));
    memset(F, 0, sizeof(F));
    sum = 0;
    sort (A + 1, A + m + 1, cmp);
    int edges = 0, i = 1;
    while (edges < n - 1)
        {
         int x = root(A[i].src);
         int y = root(A[i].dest);
         if (x != y)
            {
             V[++ edges] = A[i];
             sum += A[i].wt;
             unite(x, y);
            }
         ++ i;
        }
    m = edges;
    for (int i = 1; i <= m; ++ i)
        A[i] = V[i];
}

void solve()
{
    kruskal();
    fprintf(g, "%d\n", sum);
    for (int i = 1; i <= k; ++ i)
        {
         ++ m;
         A[m].src = readInt();
         A[m].dest = readInt();
         A[m].wt = readInt();
         kruskal();
         fprintf(g, "%d\n", sum);
        }
}

int main()
{
    read();
    solve();
    fclose(f);
    fclose(g);
    return 0;
}