首页 > 编程语言 > 详细

最小生成树一·Prim算法

时间:2015-01-02 06:24:48      阅读:310      评论:0      收藏:0      [点我收藏+]
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
#define N 1005
#define Max 11111
int mmap[N][N];
int tem[N];
int main()
{
    int n,len;
    while(~scanf("%d",&n)){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                scanf("%d",&mmap[i][j]);
            }
        }

        len=0;
        for(int i=0; i<n; i++)tem[i]=mmap[0][i];
        mmap[0][0]=-1;
        for(int kk=1; kk<n; kk++){
            int x=Max,y;
            //cout<<"!!!"<<endl;
            for(int i=0; i<n; i++){
                if(mmap[i][0]!=-1&&x>tem[i]){x=tem[i]; y=i;}
            }
            len+=x;
            //cout<<y<<endl;
            for(int i=0; i<n; i++)if(mmap[i][0]!=-1)tem[i]=min(tem[i],mmap[y][i]);
            mmap[y][0]=-1;
        }
        printf("%d\n",len);
    }
    return 0;
}

 

最小生成树一·Prim算法

原文:http://www.cnblogs.com/lveternal/p/4198102.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!