Cod sursă (job #325412)

 # include <fstream>
 # include <algorithm>
 #define nmax 121111
 using namespace std;
 ifstream f("zapada.in");
 ofstream g("zapada.out");
 struct muchie {
 int x, y, c, v;
 }u[nmax],knq[nmax];
 int n, m, k, ct, j,i, nr1, nr2,S,kn,rez,w;
 int P[nmax], T[nmax];
 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;
 u[i].v=1;
 }
  for(i=1;i<=kn;i++)
    {
        f>>knq[i].x>>knq[i].y>>knq[i].c;
        knq[i].v=0;
        T[m+i]=m+i;
    }
    rez=kn+m;
for(i=m+1;i<=rez;i++)
    u[i]=knq[i-m];
     sort(u+1, u+m+kn+1, cmp);
    w=1;
  for(i=0;i<=kn;i++)
  {
 j=1;
 ct=0;
 k=0;
 while (k < n-1) {
    if(u[j].v==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<=rez;t++)
 {
    T[t]=t;
 }
for(int t=1;t<=n;t++)
 {
     P[t]=0;
 }
 for(int t=1;t<=rez;t++)
 {
     if(knq[w].x==u[t].x&&knq[w].y==u[t].y&&knq[w].c==u[t].c&&knq[w].v==u[t].v)
     {
         knq[w].v=1;
         u[t].v=1;
         break;
     }
 }
 w++;
  }
 return 0;
 }