编写一个程序，计算给定加权图G=（V，E）的最小生成树的各边权值之和。

输入：

        第一行输入G的定点数n。接下来n行输入表示G的n*n的邻接矩阵A。A的元素aij代表顶点i到顶点j的边的权值。

另外，便不存在时记为-1.

输出：

       输出G的最小生成树的各边权值总和，占1行。

限制：

        1<=n<=100     0<=aij<=200 (aij!=-1时)    aij=aji   G为连通图。

输入示例：

5

-1    2     3     1    -1

2    -1    -1     4    -1 

3    -1    -1      1     1

1      4    1     -1     3

-1    -1    1     3    -1

输出示例：

5

 

代码：

#include
     
      using namespace std;const int maxn=100;const int INF=(1<<21);int n,M[maxn][maxn];//邻接矩阵，记录u到v的边的权值int prim(){    int u,minv;    int d[maxn]；//记录连接T内顶点与V-T内顶点的边中，权值最小的边的权值    int p[maxn];//记录最小生成树中顶点v的父节点    int color[maxn];//记录v的访问状态0 1 2    for(int i=0;i
      
       d[i]&&color[i]!=2)            {                u=i;                minv=d[i];            }        }        if(u==-1)            break;        color[u]=2;        for(int v=0;v
       
        M[u][v])                {                    d[v]=M[u][v];                    p[v]=u;                    color[v]=1;                }            }        }    }    int sum=0;    for(int i=0;i
        
         >n;    for(int i=0;i
         
          >e;            M[i][j]=(e==-1)?INF:e;        }    }    cout<
          
           <
          
         
        
       
      
     

今天也是元气满满的一天!  good luck  !