1290: Bad Cowtractors

http://tjuacm.chaosheng.top/problem.php?id=1290
https://vjudge.net/problem/POJ-2377

一开始就写好了，但是一直WA，是因为cost初始化不对，应该初始化为-INF，i==j时为0，并且有可能出现重复边，注意处理。
参考修改： https://www.cnblogs.com/wkfvawl/p/9246072.html

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1010;

int n, m, sum;
int vis[N];
int dis[N];
int cost[N][N];

void Prim(){ //从第一个点开始找周围最短的边 
    memset(dis, INF, sizeof(dis));
    for(int i = 1; i <= n; i++){
        dis[i] = cost[1][i];
        vis[i] = 0;
    }
    dis[1] = 0;
    vis[1] = 1;
    int i;
    for( i = 1; i < n; i++){ //寻找权值最小的点  
        int maxn = -INF, tmp;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && dis[j] > maxn){
                maxn = dis[j];
                tmp = j;
            }
        }
        if(maxn == -INF){ //不连通
            sum = -1; 
            break;
        }
        sum += maxn;
        vis[tmp] = 1; //把点加入生成树；
        for(int j = 1; j <= n; j++){ //利用新点改变其他不在最小生成树中的点的边
            if(!vis[j] && dis[j] < cost[tmp][j]){
                dis[j] = cost[tmp][j]; //更新 
            }
        }
    }
}

int main(){
    while(cin >> n >> m){
        sum = 0;
        int a, b, c;
        //memset(cost, -INF, sizeof(cost));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j){
                    cost[i][j] = 0;
                }else{
                    cost[i][j] = -INF;
                }
            }
        }

        for(int i = 1; i <= m; i++){
            cin >> a >> b >> c;
            if(cost[a][b] < c){  //若出现重边记录最小长度 
                cost[a][b] = cost[b][a] = c;
            }
        } 
        Prim();
        printf("%d\n", sum);
    }
    return 0;
}