Cod sursă (job #325390)

 # include <fstream>
 # include <algorithm>
 using namespace std;
 ifstream f("zapada.in");
 ofstream g("zapada.out");
 struct muchie {
 int x, y, c;
 }u[200005],knq[200005];
 int n, m, k, ct, j,i, nr1, nr2,S,kn;
 int P[200005], T[200005];
 bool cmp(muchie x, muchie y )
 {
 return x.c < y.c;
 }
 int Root(int x)
 {
 while(T[x] != x)
 x = T[x];
 return x;
 }
 void Unifica(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 main()
 {

 f>>n>>m>>kn;
 for (i=1; i<=m; ++i) {
 f>>u[i].x>>u[i].y>>u[i].c;
 T[i] = i;
 }
  for(i=1;i<=kn;i++)
    {
        f>>knq[i].x>>knq[i].y>>knq[i].c;
        T[m+i]=m+i;
    }

  for(i=0;i<=kn;i++)
  {
    if(i>=1)
        u[++m]=knq[i];
 sort(u+1, u+m+1, cmp);
 j=1;
 ct=0;
 k=0;
 while (k < n-1) {
 int rx = Root(u[j].x);
 int ry = Root(u[j].y);
 if (rx != ry){
 ++k;
 ct += u[j].c;
 Unifica(rx, ry);
 }
 ++j;
 }
 g<<ct<<'\n';
 for(int t=1;t<=m+kn;t++)
 {
    T[t]=t;
 }
for(int t=1;t<=n;t++)
 {
     P[t]=0;
 }
  }
 return 0;
 }