还是畅通工程

杭电1233

本题首先要判断两个村庄距离是否最短，其次，两村庄是否联通，即其根结点是否相同；

方法是将有联系的村庄编号存为数组，将其距离存为对应值，找出不同根结点之间的最小距离，然后相加，得出需建的最短公路；

//杭电1233
//C++提交
#include<stdio.h>
#include<string.h>
#define Max 65535
int n;
int f[101][101],set[101];
void power()
{
    int i,j,min=f[1][1],k=0,x=1,y=1,totle=0,temp;
    while(k<n-1)
    {
    
        for(i=1;i<n;i++)//用循环找出两村庄之间的最短距离，并记下村庄编号i,j,
            for(j=i+1;j<=n;j++)
            {
                if(min>f[i][j])
                {
                    min=f[i][j];
                    x=i;
                    y=j;
                }
            }
            if(set[x]!=set[y])//判断这两个村庄的根节点是否一致
            {
                k++;
                totle+=min;//记下最短公路距离和
                temp=set[y];
                for(i=1;i<=n;i++)//找出与y村庄共根结点的编号
                {
                    if(temp==set[i])
                set[i]=set[x];//将这些共根结点的编号全部置为与x共根结点
                }
            }
            min=f[x][y]=Max;//把已经记过的距离置为最大，避免下次重复
    }
    printf("%d\n",totle);
}


int main()
{
    int i,k;
    int a,b,c;
    while(scanf("%d",&n),n!=0)
    {
        for(i=1;i<=n;i++)
            set[i]=i;
        k=n*(n-1)/2;
        
        for(i=1;i<=k;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            f[a][b]=c;//把有联系的村庄存成数组，将其之间的距离赋值给数组
        }
        power();
    }
    return 0;
}