Cod sursă (job #271707)

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <ctype.h>
#define BUF_SIZE 50000

using namespace std;
FILE *f=fopen("zapada.in","r");
FILE *g=fopen("zapada.out","w");
struct muchie {unsigned short int a,b; int c; };
int n,m,k;
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;
}
muchie  mk[100005],mk1[10005];

unsigned short int t[10105],niv[10105];
inline bool cp(muchie m1,muchie m2)
{
    return m1.c<m2.c;
}
inline unsigned short int Find(unsigned short int x)
{
    while(t[x]!=0) x=t[x];
    return x;
}
inline void Union(unsigned short int x,unsigned short int y)
{ if(niv[x]>niv[y]) t[y]=x;
   else { t[x]=y;
      if(niv[x]==niv[y]) niv[y]++;
   }
}
inline void apm()
{ int mu=0,i,x,y;
    i=1;
    unsigned long long sum=0;
    while(mu<n-1)
    {
        x=Find(mk[i].a);
        y=Find(mk[i].b);
        if(x!=y)
        {mu++;
          sum+=mk[i].c;
            mk1[mu]=mk[i];
            Union(x,y);
        }
        i++;
    }
    memset(t,0,sizeof(t));
    memset(niv,0,sizeof(niv));
    fprintf(g,"%llu\n",sum);
}

int main()
{  n=read(f);
  m=read(f);
  k=read(f);
    int i,j;
    for(i=1;i<=m;i++)
    { mk[i].a=read(f);
        mk[i].b=read(f);
        mk[i].c=read(f);
    }
    sort(mk+1,mk+m+1,cp);
    apm();
    for(i=1;i<=k;i++)
    { for(j=1;j<=n-1;j++)
           mk[j]=mk1[j];

        mk[j].a=read(f);
        mk[j].b=read(f);
        mk[j].c=read(f);
        sort(mk+1,mk+n+1,cp);
        apm();
    }
    return 0;
}