Cod sursă (job #628052)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

struct drum
{
	int st, dr, cost, faza;

	bool operator<(const drum A) const
	{
		return cost < A.cost;
	}
};

int n, m, k;
drum a[101003];
int t[10003];

void Citire()
{
	int i;
	fin >> n >> m >> k;
	for (i = 1; i <= m; i++)
		fin >> a[i].st >> a[i].dr >> a[i].cost;
	for (i = m + 1; i <= m + k; i++)
	{
		fin >> a[i].st >> a[i].dr >> a[i].cost;
		a[i].faza = i - m;
	}
	m += k;
}

void Union(int x, int y)
{
	t[x] = y;
}

int Find(int x)
{
	int rad = x, y;
	while (t[rad] != 0)
		rad = t[rad];
	while (x != rad)
	{
		y = t[x];
		t[x] = rad;
		x = y;
	}
	return rad;
}

void Kruskal(int faza)
{
	int cMin, i, x, y, nrc = n;
	cMin = 0;
	for (i = 1; i <= n; i++)
		t[i] = 0;
	for(i = 1;i <= m && nrc > 1;i++)
		if (a[i].faza <= faza)
		{
			x = Find(a[i].st);
			y = Find(a[i].dr);
			if (x != y)
			{
				nrc--;
				Union(x, y);
				cMin += a[i].cost;
			}
		}
	fout << cMin << "\n";
}

void Rezolvare()
{
	int i;
	sort(a + 1, a + m + 1);
	for (i = 0; i <= k; i++)
		Kruskal(i);
}

int main()
{
	Citire();
	Rezolvare();
}