嗯...

 

题目链接：https://www.luogu.org/problemnew/show/P1546

 

首先不难看出这道题的思想是用了最小生成树，但是这道题有难点：

1.读题读不明白

2.不会读入

3.跑多了

 

针对1：

首先这道题和其他题一样，你所读入的矩阵中的每一个数字都代表着相邻两点之间的边的边权，而这个点所处的位置即可以用(i,j)来表示，然后再进行操作即可

 

针对2：

我们会发现这个N*N的矩阵是关于对角线对称的，所以我们只需要读上面一部分或者下面一部分即可（要读上面一部分读入时则特判j>i，相反则特判j<i...

 

针对3：

这里就用到了生成树的性质：n个点，n-1条边，所以在合并的时候我们定义一个k，存储合并后边的条数，每合并一次则加一，最后当k == n-1时则跳出即可

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5  6 int cnt, f[1005]; 7  8 int k, h; 9 struct node{10     int x, y, l;11 } a[110005];12 13 inline int cmp(node i, node j){14     return i.l < j.l;15 }16 17 inline int find(int x){18     if(f[x] != x)19         f[x] = find(f[x]);20     return f[x];21 }22 23 int main(){24     int n;25     int z;26     scanf("%d", &n);27     for(int i = 1; i <= n; i++){28         for(int j = 1; j <= n; j++){29             scanf("%d", &z);30             if(j > i){ //只读取上面一半有用的数据 31                 a[++cnt].x = i;32                 a[cnt].y = j;33                 a[cnt].l = z;34             }35         }36     }37     for(int i = 1; i <= n; i++)38         f[i] = i;39     sort(a+1, a+cnt+1, cmp);40     for(int i = 1; i <= cnt; i++){41         int r1 = find(a[i].x);42         int r2 = find(a[i].y);43         if(r1 != r2){44             f[r1] = r2;45             h += a[i].l;46             k++;47         }48         if(k == n-1) break;//跳出 49     }50     printf("%d", h);51     return 0;52 }