关于图论的编程题：对于一张有N个点的边带权无向完全图G,已知其的一个最小生成树为E。请求出最小边权和。

Question

如题

输入：
第1行一个数，n，表示n个点

下接n-1行，描述最小生成树，每行三个整数x,y,w，表示一条权值为w的边连接x,y两点

输出：
一个整数，就是最小边权和

数据范围：对于20%的测试点,n<=4；对于70%的测试点,n<=1000；对于100%的测试点，n<=100000
输入时w不超过int，最小边权和不超过long long。

例1：
输入：
3
1 2 3
1 3 4
输出：11
例2：
输入：
4
1 3 3
4 1 2
2 4 4
输出：20

Answer 1

说说思路：先根据输入的n构造图的邻接矩阵arcs（即n*n的二维数组），初值全部为0，并根据输入的最小生成树赋值相应元素，注意该邻接矩阵是关于主对角线对称的，即arcs[i][j]=arcs[j][i]。接下来就是对所以等于零的元素赋值（除了主对角线以为）为该元素所处的行、列的最大值。最后对数组的右上角部分求和即可。追问

虽然我不懂，但貌似是对的。如果今天中午测试通过了，就采纳你的。

追答

对不起，我编写了程序了，运行结果有误。

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int main(){
    unsigned long i,j,k,n,sum=0;
    int w,**arcs;
    scanf("%ld",&n);
    arcs=(int **)malloc(sizeof(int *)*n);
    arcs[0]=(int *)malloc(sizeof(int)*n*n);
    for(i=1;i<n;++i)arcs[i]=arcs[i-1]+n;//构造n*n的二维数组（邻接矩阵）
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            arcs[i][j]=0;
        }
    }//初始化为0
    for(k=1;k<n;++k){
        scanf("%ld%ld%d",&i,&j,&w);
        --i; --j;
        arcs[i][j]=arcs[j][i]=w;
    }//输入最小生成树
    for(i=0;i<n;++i){
        for(j=i+1;j<n;++j){
            if(arcs[i][j]){
                sum+=arcs[i][j];
                continue;
            }
            w=0;
            for(k=0;k<n;++k)if(arcs[i][k]>w)w=arcs[i][k];//查找i行的最大值
            for(k=0;k<n;++k)if(arcs[k][j]>w)w=arcs[k][j];//查找j列比w大的最大值
            sum+=arcs[i][j]=w;
        }
    }
    printf("%lu",sum);
    free(arcs[0]); free(arcs);
    printf("\nFinished!\n");
    getch();
    return 0;
}

运行那4个节点的例子，结果得到21，而不是20。看来还得修改。