Cod sursă (job #308248)

#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
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
 muchie ult;///muchia care trb adaugata

 ///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<=m)
 {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
 ///pregatim tatii si inaltimile pt noul arbore
 memset(t,0,sizeof(t));
 memset(h,0,sizeof(h));
}

void Apm()
{int i;
 int v1,v2;
 bool ok,bn;
 int start,fin;
 long long sum;
 ok=bn=0; sum=0;
 for(i=1;i<n;i++)
   {if(ult.c<a[i].c&&ok==0)
      {ok=1;
       v1=Find(ult.x);
       v2=Find(ult.y);
       if(v1!=v2)
         {Union(v1,v2);
          sum+=ult.c;
          bn=1;
          start=i;
         }
      }
    v1=Find(a[i].x);
    v2=Find(a[i].y);
    if(v1!=v2)
      {Union(v1,v2);
       sum+=a[i].c;
      }
    else fin=i;
   }
 if(bn==1)
 {for(i=fin;i>=start;i--)
      a[i]=a[i-1];
  a[start]=ult;
 }
 fprintf(g,"%d\n",sum);
 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);
 Kruskal();
 for(i=1;i<=k;i++)
   {ult.x=read(f);
    ult.y=read(f);
    ult.c=read(f);
    Apm();
   }
}

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