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

算法概述：对于一个带权的连通图，其顶点的集合 为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<n+1;i++)
      lowcost[i]=INF;
  int vnew[N+1]={0};
  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;
          }
      }
      vnew[k]=1;
      for(j=1;j<=n;i++)
      {
          if(!vnew[j]&&map[k][j]<lowcost[j])
          {
              lowcost[j]=map[k][j];
          }
      }
  }
}

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

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

代码（已ac）

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 510
#define INF 0x3f3f3f3f
using 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;
}