poj2458Highways

发表于: 2013年01月17 00:00

裸题,求最小生成树中的最大边. 下面是prim算法实现的

:::c++

#include<stdio.h>
#include<string.h>
#define MAX 505
#define INF 0x3f3f3f

int mmp[MAX][MAX];
int dis[MAX];
int vis[MAX];
int prim(int);
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int m,i,j;
        scanf("%d",&m);
        for(i=0;i<m;i++)
            for(j=0;j<m;j++)
                scanf("%d",&mmp[i][j]);
        printf("%d\n",prim(m));
    }
    return 0;
}

int prim(int m)
{
    int min,i,s,sum,ans,pp;
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    sum=1;
    for(i=0;i<m;i++)    dis[i]=INF;
    s=0;
    ans=-INF;
    while(1)
    {
        if(sum==m) break;
        min=INF;
        for(i=1;i<m;i++)
        {
            if(!vis[i] && dis[i]>mmp[s][i])//更新各点的距离
            {
                dis[i]=mmp[s][i];
            }
            if(!vis[i] && min>dis[i])
            {
                min=dis[i];
                pp=i;
            }
        }
        ans=ans>min?ans:min;
        sum++;
        s=pp;
        vis[s]=1;
    }
    return ans;
}
© 2018 - fluyy - 粤ICP备17114935号