1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6  7 #define N 505 8  9 int fa[N];10 int map[N][N];11 12 struct Path{13     int x,y,d;14     bool operator<(const Path &m)const{15         return d<m.d;16     }17 }path[250000];18 19 int getHead(int x)20 {21     int a=x;22     while(x!=fa[x]) x=fa[x];23     fa[a]=x;24     return x;25 }26 27 bool Union(int x,int y)28 {29     int fa_x=getHead(x);30     int fa_y=getHead(y);31     if(fa_x==fa_y) return false;32     fa[fa_x]=fa_y;33     return true;34 }35 36 int main()37 {38     int T,n,k,ans;39     cin>>T;40     while(T--){41         scanf("%d",&n);42         for(int i=1;i<=n;i++) fa[i]=i;//初始化父节点43         for(int i=1;i<=n;i++){44             for(int j=1;j<=n;j++)45                 cin>>map[i][j];46         }47 48         k=1;49         for(int i=1;i<=n;i++){50             for(int j=1;j<i;j++){51                 path[k].x=i,path[k].y=j;52                 path[k++].d=map[i][j];53             }54         }55 56         sort(path+1,path+k);57 58         for(int i=1;i<k;i++)59             if(Union(path[i].x,path[i].y)) ans=path[i].d;60 61         cout<<ans<<endl;62     }63     return 0;64 }

 1 #include <iostream> 2 #define MAX 502 3 using namespace std; 4 int str[MAX][MAX]; 5 bool visit[MAX];//标记数组，没有加入到树中时为false,加入了为true 6 int distan[MAX];//用以记录当前树到各个顶点的最小距离（它会被不断的更新，加入一个顶点更新一次） 7 int n; 8 int prim()//prim算法 9 {10     int v,i,j,maxi=0;11     visit[0]=true;//将第一个顶点加入树中12     for(i=0;i<n;i++)//计算只有一个顶点时的distan[i]13         distan[i]=str[0][i];14     15     for(j=1;j<n;j++)16     {17         int mini=65550;18         for (i=0;i<n;i++)//找最小的边19         {20             if(visit[i]==false&&distan[i]<mini)//找出没有在当前树中且权值最小的点21             {22                 mini=distan[i];23                 v=i;24             }25         }26         //cout<<mini<<‘ ‘;27         visit[v]=true;//标记顶点v,加入生成树中28         if(maxi<mini)29             maxi=mini;//不断更新选中路径中的最大值，以便可以直接输出30         for (i=0;i<n;i++)//将生成树的权值更新31         {32             if(visit[i]==false&&distan[i]>str[v][i])//distan[i]中始终放生成树到顶点i的最小权值,以前的自不用考虑，每次加进来一个点v，判断str[v][i]33                                                     //与distance[i]的大小，并将distance不断做更新即可34             {35                 distan[i]=str[v][i];36             }37         }38     }39     return maxi;40 }41 42 int main()43 {44     int i,j,t;45     cin>>t;46     while(t--)47     {48         cin>>n;49         for(i=0;i<n;i++)50             visit[i]=false;51         for(i=0;i<n;i++)52             for(j=0;j<n;j++)53                 scanf("%d",&str[i][j]);54             cout<<prim()<<endl;55     }56     return 0;57 }