【解題思路】

最小生成樹模板題，求最小生成樹所有邊權加和。
該題輸入的是鄰接矩陣，因此使用鄰接矩陣解決該問題。當然也可以保存為鄰接表。

【參考代碼】

//示例代碼  Prim算法
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;const int N=105;   // 定義常量 N，表示數組大小
int n;
int g[N][N];       // 保存圖的鄰接矩陣
int minn[N];       // 保存當前已經選定的點到其它點的最小邊權值
bool v[N];         // 標記哪些點已經在MST中int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>g[i][j];memset(minn,0x3f,sizeof(minn));    // 將minn數組初始化為最大值minn[1]=0;                         // 從1號結點開始建立MSTmemset(v,true,sizeof(v));         // 將所有結點標記為未被訪問過for(int i=1;i<=n;i++){            // 構建n個頂點的MSTint k=0;for(int j=1;j<=n;j++)          // 找到目前離MST最近的點if(v[j]&&(minn[j]<minn[k])) k=j;v[k]=false;                   // 將點k加入MST中for(int j=1;j<=n;j++)          // 更新minn數組if(v[j]&&(g[k][j]<minn[j])) minn[j]=g[k][j];}int ans=0;                        // 計算MST的總邊權值for(int i=1;i<=n;i++) ans+=minn[i];cout<<ans;                        // 輸出結果return 0;
}