1.cpp

hdu 上的题 继续畅通工程 可以AC 初学者的水平 请见谅

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

#define N 100
#define M N*(N-1)/2

struct Road
{
       int a;
       int b;
       int v;
       }road[M];
int pre[N];
int rank[N];
void init (int n)
{
    for(int i=0;i<=n;i++)
    {
            pre[i]=-1;
            rank[i]=1;
    }
}
int find(int a)
{
    if(pre[a]==-1)
    return  a;
    else
    return pre[a]=find(pre[a]);
}
void Union (int a,int b)
{
     a=find(a);
     b=find(b);
     if(a==b)
     return ;

     int tmp=rank[a]+rank[b];
     if(rank[a]<rank[b])
     {
            pre[a]=b;
            rank[b]=tmp;
     
     }
     else
     {
         pre[b]=a;
         rank[a]=tmp;
     }
}
int cmp(const void *a,const void *b)
{
    return (*(Road *)a).v-(*(Road *)b).v;
}

int main()
{
    int n,m,a,b,bl;
    while(scanf("%d",&n),n)
    {
          m=n*(n-1)/2  ;
          init(n);
          for(int i=0;i<m;i++)
          {
                  scanf("%d%d%d%d",&a,&b,&road[i].v,&bl);
                  road[i].a=a;
                  road[i].b=b;
                  if(bl && a!=b)
                  {
                       Union(a,b);
                  }
          }
          int min=0;
          qsort(road,m,sizeof(road[0]),cmp);
          for(int i=0;i<m;i++)
          {
                  if(find(road[i].a)!=find(road[i].b))
                  {
                       min+=road[i].v;
                       Union(road[i].a,road[i].b);
                  }
          }
          printf("%d\n",min);
    }
    system("pause");
    return 0;
}