two.c

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

/*
DMIH 2002, Drugi dan natjecanja
Srednjoskolska skupina, II. podskupina
Zadatak DVIJE, Programski jezik C
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct li{
  int np;
  int *p;
  int *l;
} np;

int maxput=0;

np put[10005];
int rk[10005];

int ukput(int tren, int od)
{
  int i;
  np tp;
  int p=0;

  tp=put[tren];
  for(i=0;i<tp.np;i++){
    if(tp.p[i]==od)
      continue;
    p+=tp.l[i]+ukput(tp.p[i],tren);
  }

  return p;
}

int rek(int tren,int od)
{
  np tp;
  int i;
  int maxdub=0,dd=0;
  int dub,dp;

  if (rk[tren]>=0) return rk[tren];
  tp=put[tren];

  if(tp.np==1&&od)
    return 0;
  if(tp.np==1){
    rk[tren]=rek(tp.p[0],tren)+tp.l[0];
    return rk[tren];
  }
  if(tp.np==2){
    if(od){
      if(tp.p[0]==od)
        rk[tren]=rek(tp.p[1],tren)+tp.l[1];
      else
        rk[tren]=rek(tp.p[0],tren)+tp.l[0];
      return rk[tren];
    }
    else
      return rek(tp.p[0],tren)+rek(tp.p[1],tren)+tp.l[1]+tp.l[0];
  }
  for(i=0;i<tp.np;i++){
    if(tp.p[i]==od)
      continue;
    dub=tp.l[i]+rek(tp.p[i],tren);
    if(dub>maxdub){
      maxdub=dub;
      dp=i;
    }
  }
  for(i=0;i<tp.np;i++){
    if(tp.p[i]==od)
      continue;
    dub=tp.l[i]+rek(tp.p[i],tren);
    if(dub>dd && i!=dp)
      dd=dub;
  }
  if(dd+maxdub>maxput)
    maxput=dd+maxdub;

  return maxdub;
}

int main(void)
{
  FILE *in,*out;
  int fr,to,len;
  int c;
  int poc;
  int i;
  int nvrh;

  in=fopen("two.in","r");
  out=fopen("two.out","w");
  fscanf(in,"%d",&nvrh);
  fscanf(in,"%d",&poc);
  for(i=1;i<=nvrh;i++)
    put[i].p=NULL;
  for(i=1;i<nvrh;i++){
    fscanf(in,"%d %d %d",&fr,&to,&len);
    put[fr].p=realloc(put[fr].p,(++put[fr].np)*4);
    put[to].p=realloc(put[to].p,(++put[to].np)*4);
    put[fr].l=realloc(put[fr].l,(put[fr].np)*4);
    put[to].l=realloc(put[to].l,(put[to].np)*4);
    put[fr].p[put[fr].np-1]=to;
    put[to].p[put[to].np-1]=fr;
    put[fr].l[put[fr].np-1]=len;
    put[to].l[put[to].np-1]=len;

  }

  for(i=1;i<=nvrh;i++)
    rk[i]=-1;

  if((c=rek(1,0))>maxput)
    maxput=c;
  fprintf(out,"%d\n",2*ukput(1,0)-maxput);
  fclose(out);
  return 0;
}