Cod sursă (job #571741)

#include <fstream>
#include <algorithm>
#include <string.h>

#define NMAX 10005
#define MMAX 1000005
#define MAX_SIZE 150000

using namespace std;

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

struct Edge{
    short from;
    short to;
    int cost;
};

short n, k;
int m, max_cost, answer;
int pos = MAX_SIZE - 1;
short root[NMAX];
char buffer[MAX_SIZE + 5];
Edge v[MMAX];

short getRoot(short x)
{
    short found = 0;
    short it = x;

    while(root[it] != 0)
        it = root[it];
    found = it;
    it = x;
    while(root[it] != 0)
    {
        short aux = root[it];
        root[it] = found;
        it = aux;
    }

    return found;
}
void getAnswer()
{
    short pos = 0;
    answer = 0;
    memset(root, 0, sizeof(root));

    for(int i = 1; i <= m && pos <= n - 1; i++)
    {
        short root_start = getRoot(v[i].from);
        short root_finish = getRoot(v[i].to);

        if(root_start != root_finish)
        {
            root[root_start] = root_finish;
            v[++pos] = v[i];
            answer = answer + v[i].cost;
            max_cost = max(max_cost, v[i].cost);
        }
    }
    m = pos;

    g << answer << "\n";
}

int read()
{
    int x = 0;

    while(!isdigit(buffer[pos]))
    {
        pos++;
        if(pos == MAX_SIZE)
        {
            f.read(buffer, MAX_SIZE);
            pos = 0;
        }
    }
    while(isdigit(buffer[pos]))
    {
        x = x * 10 + (buffer[pos] - '0');
        pos++;
        if(pos == MAX_SIZE)
        {
            f.read(buffer, MAX_SIZE);
            pos = 0;
        }
    }

    return x;
}

bool cmp(Edge a, Edge b)
{
    return a.cost < b.cost;
}

int main()
{
    n = read();
    m = read();
    k = read();
    for(int i = 1; i <= m; i++)
    {
        v[i].from = read();
        v[i].to = read();
        v[i].cost = read();
    }

    sort(v + 1, v + m + 1, cmp);
    getAnswer();
    for(int year = 1; year <= k; year++)
    {
        m++;
        v[m].from = read();
        v[m].to = read();
        v[m].cost = read();

        if(v[m].cost < max_cost)
        {
            for(int i = m - 1; i >= 1 && v[i + 1].cost < v[i].cost; i--)
                swap(v[i], v[i + 1]);
            getAnswer();
        }
        else
            g << answer << "\n";
    }

    return 0;
}