标题:最小生成树prim算法
取消只看楼主
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
结帖率:79.37%
已结贴  问题点数:20 回复次数:0 
最小生成树prim算法
题目:http://www.
这道题需要用prim算法解决,可是代码写好了以后不管怎么测试,结果输出都是4,请各位高手帮我看看
输入:
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出:
28

代码:
#include <stdio.h>
#include <stdlib.h>
#define MAX 999999
int dis[100];
void prim(long map[100][100],int n,int start)
{
    int mark[100];
    int i,j,k,min,sum=0;
    for(i=0;i<n;i++)
    {
    mark[i]=0;
    dis[i]=map[start][i];
    }
    mark[start]=1;dis[start]=0;
    for(i=0;i<n;i++)
    {
    min=MAX;
    for(j=0;j<n;j++)
    if(mark[j]==0&&dis[j]<min)
    {
    min=dis[j];
    k=j;
    }
    if(min==MAX) break;
    sum=sum+min;
    for(j=0;j<n;j++)
    if(mark[j]==0&&dis[j]>map[k][j])
    dis[j]=map[k][j];
    }
    printf("%d\n",sum);
}
int main()
{
    long map[100][100];
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<100;i++)
    for(j=0;j<100;j++)
    map[i][j]=MAX;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    scanf("%ld",&map[i][j]);
    prim(map,n,0);
    system("pause");
    return 0;
}
搜索更多相关主题的帖子: 测试 include start 
2011-04-04 19:52



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-335628-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.839997 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved