Cod sursă (job #271941)

 #include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <cstring>
#define BUF_SIZE 50000
using namespace std;

FILE *f=fopen("zapada.in","r");
FILE *g=fopen("zapada.out","w");

struct muchie
{unsigned short x,y; int c;};

muchie a[101005],b[101005];
unsigned short int t[10105],h[10105];
int n,m,k,ct;
unsigned short int nrmsel;

int pos=BUF_SIZE;
char buf[BUF_SIZE];

inline char getChar(FILE *f)
{if (pos==BUF_SIZE)
  {fread(buf, 1, BUF_SIZE, f);
   pos=0;
  }
return buf[pos++];
}

inline int read(FILE *f)
{
int result = 0;
char c;
do {c=getChar(f);}
while (!isdigit(c));

do {result=10*result+c-'0';
    c=getChar(f);
    }
while (isdigit(c));

return result;
}

inline bool comp(muchie m1,muchie m2)
{
return m1.c<m2.c;
}
unsigned short int  Find(int x)
{
while(t[x]!=0) x=t[x];
return x;
}
void Union(unsigned short int  x,unsigned short int y)
{ if(h[x]>h[y]) t[y]=x;
else {t[x]=y;
      if(h[x]==h[y]) h[y]++;
     }
}
void Kruskal()
{nrmsel=0;
int i,x1,x2;
long long scost=0;
i=1;
while(i<=n&&nrmsel<n-1)
   {x1=Find(a[i].x);
    x2=Find(a[i].y);
    if(x1!=x2)
     {b[++nrmsel]=a[i];
      scost+=a[i].c;
      Union(x1,x2);
     }
    i++;
   }
fprintf(g,"%d\n",scost);
for(i=1;i<=nrmsel;i++)
   a[i]=b[i];
memset(t,0,sizeof(t));
memset(h,0,sizeof(h));
}
int main()
{int i,j;
n=read(f);
m=read(f);
k=read(f);
for(i=1;i<=m;i++)
  {a[i].x=read(f);
   a[i].y=read(f);
   a[i].c=read(f);
  }
sort(a+1,a+m+1,comp);
Kruskal();
ct=nrmsel;
for(i=1;i<=k;i++)
  {ct++;
   a[ct].x=read(f);
   a[ct].y=read(f);
   a[ct].c=read(f);
   sort(a+1,a+ct+1,comp);
   n++;
   Kruskal();
  }
return 0;
}