這題其實(shí)當(dāng)時(shí)就應(yīng)該想到，但只想到kruskal的程度，覺(jué)得不對(duì)，就沒(méi)敢敲。看了下解題報(bào)告，原來(lái)可以巧妙的利用一下n號(hào)集合，怎么說(shuō)呢，把邊從大到小排序，然后像做最大生成樹(shù)那樣增加邊。
1.如果兩個(gè)頂點(diǎn)在同一集合，就把這個(gè)集合同一掛到n號(hào)集合下面去，由于題目中沒(méi)有n這個(gè)點(diǎn)，所以?huà)煸趎下的就算找到圈了。
2.如果兩個(gè)頂點(diǎn)不在同一集合,且兩個(gè)頂點(diǎn)都不在n集合，那么請(qǐng)隨意:-)。
3.如果有一個(gè)頂點(diǎn)在n集合中，這里要特別注意，害我RE了無(wú)數(shù)回，要把不是n的那個(gè)集合掛到n下面去。想想嘛，本來(lái)找到圈了，結(jié)果掛到0-n-1下面，又會(huì)認(rèn)定為沒(méi)有圈了。
（此題算法參考了標(biāo)程，但是標(biāo)程寫(xiě)得實(shí)在太挫了，好像故意要讓人看不懂似的，跟tc里的變態(tài)們一個(gè)樣，難道標(biāo)程就不應(yīng)該寫(xiě)的友好一點(diǎn)？bsz）
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node
{
int a;
int b;
int v;
bool operator<(node other)
{return v<other.v;}
}e[2000010];
int ans;
int f[100100];
int r[100000];
int n,m;
int find(int x)
{
if(f[x]==x)
return x;
else f[x]=find(f[x]);
return f[x];
}
int main()
{
//freopen("Pseudoforest.in","r",stdin);
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
if(n==0&&m==0) break;
for(i=0;i<=n;i++)
f[i]=i;
for(i=0;i<m;i++)
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
sort(e,e+m);
for(i=m-1;i>=0;i--)
{
int a=find(e[i].a);
int b=find(e[i].b);
if(a>b)
swap(a,b);
if(a!=b)
{
ans+=e[i].v;
f[a]=b;
}
else if(a==b&&b!=n)
{
ans+=e[i].v;
f[a]=n;
}
}
printf("%d\n",ans);
}
return 0;
}