Cod sursă (job #308246)

#include <ctype.h>///pentru isdigit
#include <string.h>///pentru memset
#include <algorithm>///pentru sort
#include <fstream>
#define nmax 10005
#define mmax 100005
#define BUF_SIZE 50000
using namespace std;
FILE *f=fopen("zapada.in","r");
FILE *g=fopen("zapada.out","w");
int n,m,k; ///date de intrare
int nr;
unsigned short int t[nmax];///tatal
unsigned short int h[nmax];///inaltimea arborelui


struct muchie
{unsigned short int x,y;
 int c;};
 muchie a[mmax];///graful initial, ulterior cel din care extragem apm
 muchie b[mmax];///apm auxiliar

 ///parsare
int pos=BUF_SIZE;
char buf[BUF_SIZE];///tot din fisier

inline char getChar(FILE *f)
{if(pos==BUF_SIZE) ///daca citim pt prima oara
  {fread(buf,1,BUF_SIZE,f); ///citim fisierul
   pos=0; ///pos se muta pe prima pozitie a sirului
  }
 return buf[pos++];///returnam pozitia curenta
}

inline int read(FILE *f)
{int result=0;
 char c;
 do
  {c=getChar(f);}
 while(!isdigit(c));///cat timp c nu e cifra
 do
  {result= result*10+c-'0';///punem in result numarul
   c=getChar(f);
  }
 while(isdigit(c));///cat timp c e cifra
 return result;
}

///fct pt sortarea datelor de timp struct
inline bool comp(muchie a, muchie b)
{return a.c<b.c;}

unsigned short int Find(unsigned short x)
{while(t[x]!=0) x=t[x];
 return x;}

void Union(unsigned short int i, unsigned short int j)
{if(h[i]>h[j]) t[j]=i;
 else
 {t[i]=j;
  if(h[i]==h[j]) h[j]++;}///j e tata de mai multe ori
}


void Kruskal()
{int i=1;
 unsigned short int Muchie;
 int v1,v2;
 long long s;
 Muchie=0; s=0;
 while(Muchie<n-1&&i<=nr)
 {v1=Find(a[i].x);///tatal lui x
  v2=Find(a[i].y);///tatal lui y
  if(v1!=v2)///daca sunt diferiti
   {b[++Muchie]=a[i];///adaugam muchia
    s+=a[i].c;///crestem costul
    Union(v1,v2);///ii unim pe tati
   }
  i++;
 }
 fprintf(g,"%d\n",s);///afisam costul din acel an
 for(i=1;i<=Muchie;i++)
    a[i]=b[i];///punem in a apm-ul calculat
 nr=n-1;///n-1 este nr-ul de muchii dintr-un apm
 ///pregatim tatii si inaltimile pt noul arbore
 memset(t,0,sizeof(t));
 memset(h,0,sizeof(h));
}

void Read()
{int i;
 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);
    }
 ///sortam muchiile dupa cost
 sort(a+1,a+m+1,comp);
 nr=m;///initial sunt m muchii
 Kruskal();
 for(i=1;i<=k;i++)
   {nr++;
    a[nr].x=read(f);
    a[nr].y=read(f);
    a[nr].c=read(f);
    sort(a+1,a+nr+1,comp);
    Kruskal();
   }
}

int main()
{Read();
 return 0;
}