算法学习之路|最小生成树—

算法概述：对于一个带权的连通图，其顶点的集合为V，边的集合为E。定义一个新的集合Vnew={空}，第一步在图中任选一个顶点v加入Vnew，第二步寻找最短的边(u,v),其中u∈Vnew，v∈V-Vnew，其中v加入Vnew，循环执行第二步直到Vnew=V结束。

void prime(){  int i,j;  int min=INF;  for(i=1;i
    
     lowcost[j])          {              min=lowcost[j];              k=j;          }      }      vnew[k]=1;      for(j=1;j<=n;i++)      {          if(!vnew[j]&&map[k][j]

题目大意：n个城市，知道各个城市的距离，建路将n个城市互相可达，路是直线建的，max=各个城市最长的那条路，求所有建路方案中max的最小值。

解题思路：直接prime求最小生成树

代码（已ac）

#include
    
     #include
     
      #include
      
       #define N 510#define INF 0x3f3f3f3fusing namespace std;int _map[N][N];int Vnew[N];int lowcost[N];int prime(int n){    int i,j;    int _min;    int ans=-1;    for(i=1;i<=n;i++)        lowcost[i]=INF;    lowcost[1]=0;    memset(Vnew,0,sizeof(Vnew));    for(i=1;i<=n;i++)    {        int k;        _min=INF;        for(j=1;j<=n;j++)         {             if(!Vnew[j]&&_min>lowcost[j])            {                _min=lowcost[j];                k=j;            }        }        ans=max(ans,_min);        Vnew[k]=1;        for(j=1;j<=n;j++)         {             if(!Vnew[j]&&lowcost[j]>_map[k][j])            {                lowcost[j]=_map[k][j];            }        }    }    return ans;}int main (void){    int T,i,j;    int k;    scanf("%d",&T);    int n;    while(T--)    {        scanf("%d",&n);        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)                scanf("%d",&_map[i][j]);        k=prime(n);        printf("%d\n",k);    }    return 0;}