POJ 1258 Agri-Net

Description

Input

Output

Sample Input

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

Sample Output

28

Source

题意：还用说嘛。

思路：最小裸题，还用说嘛。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stdlib.h>

using namespace std;

int mp[105][105];
int low[105];
bool vis[105];
int n;

int prim(){
    int pos,minx,res=0;
    memset(vis,false,sizeof(vis));
    vis[1]=true;
    pos=1;
    for(int i=1;i<=n;i++){
        if(i!=pos)
            low[i]=mp[pos][i];
    }
    for(int i=1;i<n;i++){
        minx=10000000;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&minx>low[j]){
                minx=low[j];
                pos=j;
            }
        }
        res+=minx;
        vis[pos]=true;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&low[j]>mp[pos][j])
                low[j]=mp[pos][j];
        }
    }
    return res;
}

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

POJ 1258 Agri-Net,布布扣,bubuko.com

POJ 1258 Agri-Net

原文：http://blog.csdn.net/kimi_r_17/article/details/38333285