Cod sursă (job #626183)

#include <fstream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
multimap <int, pair <int, int>> pam;
ifstream fin("zapada.in");
ofstream fout("zapada.out");
int n, m, k, currentout, i, j, x, y, z;
vector <int> viz;
vector <vector <pair <int, int>>> v;
vector <int> t, p;
int root(int b)
{
    while (b != t[b])
        b = t[b];
    return b;
}
void unificare(int x, int y)
{
    if (p[x] < p[y])
        t[x] = y;
    if (p[x] > p[y])
        t[y] = x;
    if (p[x] == p[y])
    {
        t[y] = x;
        p[x]++;
    }
}
int snow()
{
    int q = 1; z = 0;
    int cost = 0;
    multimap<int, pair<int, int>>::iterator it;
    it = pam.begin();
    t.resize(n + 1); p.resize(1); p.resize(n + 1);
    for (int i = 1; i <= n; i++)
        t[i] = i;
    while (z < n - 1)
    {
        x = (*it).second.first;
        y = (*it).second.second;
        int rx = root(x), ry = root(y);
        if (rx != ry)
        {
            ++z;
            cost += (*it).first;
            unificare(rx, ry);
        }
        it++;
    }
    return cost;
}
bool canBeAdded (int x, int y, int z)
{
    vector <int> vis (n+1, 0);
    vis[x] = 1;
    queue <int> qu;
    qu.push(x);
    int pas = 0;
    int ct = 0, mt = 1e9;
    bool ok = false;
    while (!qu.empty())
    {
        pas = qu.front();
        qu.pop();
        for (int u = 0; u < v[pas].size(); u++)
        {
            if (vis[v[pas][u].first] == 0)
            {
                qu.push(v[pas][u].first);
                vis[v[pas][u].first] = vis[pas]+1;
            }
            if (v[pas][u].first == y)
            {
                ok = 1; break;
            }
        }
        if (ok) break;
    }
    queue <int> qq;
    int cpos;
    qq.push(y);
    while (!qq.empty())
    {
        cpos = qq.front();
        qq.pop();
        for (int i = 0; i < v[cpos].size(); i++)
        {
            if (-vis[v[cpos][i].first] + vis[cpos] == 1 && vis[v[cpos][i].first] != 0)
            {
                ct += v[cpos][i].second;
                if (mt > v[cpos][i].second) mt = v[cpos][i].second;
                qq.push(v[cpos][i].first);
            }
        }
    }
    if (ct-mt <= z) return 0;
    return 1;
}
int main()
{
    fin >> n >> m >> k; v.resize(n+1);
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        pam.insert(make_pair(z, make_pair(x, y)));
    }
    int q = 1; z = 0;
    int cost = 0;
    multimap<int, pair<int, int>>::iterator it;
    it = pam.begin();
    t.resize(n + 1); p.resize(1); p.resize(n + 1);
    for (int i = 1; i <= n; i++)
        t[i] = i;
    while (z < n - 1)
    {
        x = (*it).second.first;
        y = (*it).second.second;
        int rx = root(x), ry = root(y);
        if (rx != ry)
        {
            ++z;
            v[x].push_back(make_pair(y, (*it).first));
            v[y].push_back(make_pair(x, (*it).first));
            cost += (*it).first;
            unificare(rx, ry);
        }
        it++;
    }
    currentout = cost;
    fout << currentout << "\n";
    for (i = 1; i <= k; i++)
    {
        fin >> x >> y >> z;
        if (canBeAdded(x, y, z))
        {
            v[x].push_back(make_pair(y, z));
            v[y].push_back(make_pair(x, z));
            pam.insert(make_pair(z, make_pair(x, y)));
            currentout = snow();
        }
        fout << currentout << "\n";
    }
    return 0;
}