#include<cstdio> #include<cstring> #define INF 0x3f3f3f3f using namespace std; //prim算法,没有很难,再看看就好了 int matrix[105][105]; int dis[105]; bool vis[105]; int n; void prim() { memset(vis,0,sizeof(vis)); int ans = 0,Min,tmp; vis[0] = 1; for(int i = 0; i<n; ++i) dis[i] = matrix[0][i]; for(int i = 1; i<n; ++i) { Min = INF; for(int j = 1; j<n; ++j) { if(!vis[j]&&Min>dis[j]) { Min = dis[j]; tmp = j; } } vis[tmp] = 1; //重点,加完点要更新所有点的距离 for(int i = 0; i<n; ++i) { if(!vis[i]&&dis[i]>matrix[tmp][i]) dis[i] = matrix[tmp][i]; } } for(int i = 0; i<n; ++i) ans += dis[i]; printf("%d\n",ans); } int main() { while(~scanf("%d",&n)) { for(int i = 0; i<n; ++i) for(int j = 0; j<n; ++j) scanf("%d",&matrix[i][j]); prim(); } return 0; }