首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Prime最小生成树(个人模板)

Prime最小生成树(个人模板)

作者头像
owent
发布2018-08-01 17:37:43
3220
发布2018-08-01 17:37:43
举报
文章被收录于专栏:owentowent
//Prime连通路模块
#define N 1000         //最大数据规模
#define MAXNUM 3000000   //最大路径长度
typedef double PrimeType;//路径类型

PrimeType PrimeRecord[N];
PrimeType dis[N][N];
int isLined[N] = {1,0};

PrimeType GetPrimeLength(const long n)
{
    PrimeType tmpLen = MAXNUM;
    long tmpPos = 0,left = n - 1;
    PrimeType sumLen = 0;

    for(long i = 1 ; i < n ; i ++)
        PrimeRecord[i] = dis[0][i];
    while(left --)
    {
        tmpLen = MAXNUM;
        for(long i = 1 ; i < n ; i ++)
            if(!isLined[i] && PrimeRecord[i] < tmpLen)
                tmpPos = i,tmpLen = PrimeRecord[i];

        sumLen += tmpLen;
        isLined[tmpPos] ++;
        for(long i = 1 ; i < n ; i ++)
            if(dis[tmpPos][i] < PrimeRecord[i])
                PrimeRecord[i] = dis[tmpPos][i];
    }

    return sumLen;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2009-09-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档