POJ 2377

最大生成树

//4088K    79MS

#include <iostream>
#include <stdio.h>
using namespace std;

const int MN=1001;
const int MM=20001;

int Map[MN][MN];
bool visited[MN];
int dist[MN];

int M,N;
int ans=0;
bool wrong=false;

void Prim(int s)
{
    memset(visited,false,sizeof(visited));
    
    visited[s]=true;
    for(int i=1;i<=N;i++)
        dist[i]=Map[s][i];

    int Num=1;
    while(Num<N){
        int tag=-1;
        int Max=INT_MIN;
        for(int i=1;i<=N;i++){
            if(!visited[i]){
                if(dist[i]>Max){
                    Max=dist[i];
                    tag=i;
                }
            }
        }
        if(Max==-1)
        {
            wrong=true;
            return;
        }
        visited[tag]=true;
        ans+=Max;
        Num++;
        for(int i=1;i<=N;i++){
            if(Map[tag][i]>dist[i]&&Map[tag][i]!=-1
               &&(!visited[i])){
                dist[i]=Map[tag][i];
            }
        }
    }
}

            
int main()
{
    scanf("%d%d",&N,&M);
    int x,y,v;
    for(int i=0;i<MN;i++)
        for(int j=0;j<MN;j++)
            Map[i][j]=-1;
    for(int i=1;i<=M;i++){
        scanf("%d%d%d",&x,&y,&v);
        if(v>Map[x][y])
            Map[x][y]=v;
        if(v>Map[y][x])
            Map[y][x]=v;
    }
    int source=x;
    Prim(source);
    if(!wrong)
        printf("%d\n",ans);
    else
        printf("-1\n");
    return 0;
}