Sample Input
1 //T
3 //n
0 990 692 //邻接矩阵
990 0 179
692 179 0
Sample Output
692
prim
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <cmath> 6 # define LL long long 7 using namespace std ; 8 9 const int INF=0x3f3f3f3f; 10 const int MAXN=510; 11 bool vis[MAXN]; 12 int lowc[MAXN]; 13 int n ; 14 int cost[MAXN][MAXN] ; 15 int MAX = 0 ; 16 17 int Prim()//点是0~n-1 18 { 19 int ans=0; 20 memset(vis,false,sizeof(vis)); 21 vis[0]=true; 22 for(int i=1;i<n;i++)lowc[i]=cost[0][i]; 23 for(int i=1;i<n;i++) 24 { 25 int minc=INF; 26 int p=-1; 27 for(int j=0;j<n;j++) 28 if(!vis[j]&&minc>lowc[j]) 29 { 30 minc=lowc[j]; 31 p=j; 32 } 33 if(minc==INF)return -1;//原图不连通 34 ans+=minc; 35 if (minc > MAX) 36 MAX = minc ; 37 vis[p]=true; 38 for(int j=0;j<n;j++) 39 if(!vis[j]&&lowc[j]>cost[p][j]) 40 lowc[j]=cost[p][j]; 41 } 42 return ans; 43 } 44 45 int main() 46 { 47 48 // freopen("in.txt","r",stdin) ; 49 int T ; 50 cin>>T ; 51 while(T--) 52 { 53 cin>>n ; 54 int w ; 55 int i , j ; 56 for (i = 0 ; i < n ; i++) 57 for (j = 0 ; j < n ; j++) 58 { 59 cin>>w ; 60 if(w==0) 61 cost[i][j] = INF ; 62 else 63 cost[i][j] = w ; 64 } 65 MAX = 0 ; 66 Prim() ; 67 cout<<MAX<<endl ; 68 69 } 70 return 0 ; 71 }