1289: Agri-Net

http://tjuacm.chaosheng.top/problem.php?id=1289
https://vjudge.net/problem/POJ-1258
参考
https://blog.csdn.net/queen00000/article/details/81281823

最小生成树
这里用prim算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f;
const int N = 110;

int n, sum;
int vis[N];
int dis[N];
int matrix[N][N];

void Prim(){ //从第一个点开始找周围最短的边 

    for(int i = 1; i <= n; i++){
        dis[i] = matrix[1][i];
        vis[i] = 0;
    }
    //printf("yes");
    dis[1] = 0;
    vis[1] = 1;

    for(int i = 1; i < n; i++){ //寻找权值最小的点  
        int minn = INF, tmp;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && dis[j] < minn){
                minn = dis[j];
                tmp = j;
            }
        }
            sum += minn;
            vis[tmp] = 1; //把点加入生成树；
            for(int j = 1; j <= n; j++){ //利用新点改变其他不在最小生成树中的点的边
                if(!vis[j] && dis[j] > matrix[tmp][j]){
                    dis[j] = matrix[tmp][j]; //更新 
                }
            }
    }
}

int main(){
    while(cin >> n){
        sum = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cin >> matrix[i][j];
            }
        }
        //printf("yes\n");
        Prim();
        printf("%d\n", sum);
    }
    return 0;
}