hdu3367.cpp

//#include <bits/stdc++.h>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <cstdlib>
#include <set>
#include <sstream>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
#include <time.h>
#define PI 3.14159265
#define N 100000+5
#define ll long long
#define INF 2147483647
using namespace std;
int n,m,p[N],has_cycle[N],x,y,ans,cnt;

struct E{ int x, y, c; } e[N];

void init(){ for(int i=0;i<n;i++) p[i]=i, has_cycle[i]=0; ans=0; cnt=0;}

int findd(int x){ return (x==p[x])?x:findd(p[x]); }

void uni(int x,int y){ p[x]=y; }//固定設y為parent

bool cmp(E e1,E e2){ return e1.c>e2.c; }

int main(){
    while(scanf("%d%d",&n,&m) && n+m){
        init();
        for(int i=0;i<m;i++) {
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
        }
        sort(e,e+m,cmp);
        for(int i=0;i<m;i++){
            x=findd(e[i].x); y=findd(e[i].y);//以下全部用parent做判斷比較方便
            if(x!=y){ //x,y不在同一棵樹時
                if(has_cycle[x]&&has_cycle[y]) continue;//兩棵樹各有一個環 在連接則共有兩個環
                uni(x,y);
                if(has_cycle[x]||has_cycle[y]) has_cycle[y]=1;//若其中一棵樹裡有環 則合併後有環
                ans+=e[i].c;
                cnt++;
            }
            else{
                if(has_cycle[x]) continue;//已經有一個環了 不能再連接
                has_cycle[x]=1;//同一棵樹理兩點再連接必成還
                ans+=e[i].c;
                cnt++;
            }
            if(cnt==n) break;//跑完n-1個邊之後結束
        }
        printf("%d\n",ans);
    }
}