开发者社区人工智能文章正文

POJ1258 Agri-Net【最小生成树】

2017-11-13 909

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

Problem:1258		User: qq1203456195
Memory: 208K		Time: 16MS
Language: C		Result: Accepted



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 105
#define MAX 100005
int visited[N],closet[N],Metr[N][N];
int n;
int prim()
{
    int i,ms,next,sum,j;
    memset(visited,0,sizeof(visited));
    for (i=0;i<n;i++)
        closet[i]=Metr[0][i];
    visited[0]=1;
    sum=0;
    for (j=1;j<n;j++)
    {
        ms=MAX;
        for (i=0;i<n;i++)
        {
            if (!visited[i]&&closet[i]<ms)
            {
                ms=closet[i];
                next=i;
            }
        }
        sum+=ms;
        visited[next]=1;
        for (i=0;i<n;i++)
            if (!visited[i]&&Metr[next][i]<closet[i])
                closet[i]=Metr[next][i];

    }
    return sum;
}
int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
                scanf("%d",&Metr[i][j]);
        printf("%d\n",prim());
    }
    return 0;
}