Cod sursă (job #804433)

#include <fstream>
#include <vector>
#include <map>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

ifstream fin("blis.in");
ofstream fout("blis.out");
int n, m, q;
struct muchie
{
    int x, y, c;
    bool operator <(const muchie& other)const
    {
        return (*this).c < other.c;
    }
};
muchie a[100005];
int t[10005], r[10005];
map<pair<int, int>,pair<bool,int>> M;
int find(int x)
{
    if (t[x] == 0)
        return x;
    int y = find(t[x]);
    t[x] = y;
    return y;
}
void Union(int x, int y)
{
    if (r[x] > r[y])
        t[y] = x;
    else
    {
        t[x] = y;
        if (r[x] == r[y])
            r[y]++;
    }
}

int main()
{
    fin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
        fin >> a[i].x >> a[i].y >> a[i].c;
    sort(a + 1, a + m + 1);
    int s = 0;
    int k = 0;
    for (int i = 1; i <= m; i++)
    {
        int x = find(a[i].x);
        int y = find(a[i].y);
        if (x != y)
        {
            M[{a[i].x, a[i].y}] = { 1,a[i].c };
            M[{a[i].y, a[i].x}] = { 1,a[i].c };
            s += a[i].c;
            Union(x, y);
        }
    }
    fout << s<<"\n";
    while(q--)
    {
        muchie val;
        fin >> val.x >> val.y >> val.c;
        int maxx = 0, nod1=0, nod2=0;
        for (int i = 1; i <= n; i++)
        {
            if (M[{i, val.x}].first && M[{i, val.y}].first)
            {
                if (M[{i, val.x}].second > M[{i, val.y}].second && M[{i, val.x}].second > maxx)
                {
                    maxx = M[{i, val.x}].second;
                    nod1 = i;
                    nod2 = val.x;
                }
                else if(M[{i, val.x}].second <= M[{i, val.y}].second && M[{i, val.y}].second < maxx)
                {   
                    maxx = M[{i, val.y}].second;
                    nod1 = i;
                    nod2 = val.y;
                }
            }
        }
        if (maxx > val.c)
        {
            s -= maxx;
            M[{nod1, nod2}] = { 0,0 };
            M[{nod2, nod1}] = { 0,0 };
            M[{val.x, val.y}] = { 1,val.c };
            M[{val.y, val.x}] = { 1,val.c };
            s += val.c;
        }
        fout << s<<"\n";
    }
    return 0;
}