学步园

Description

Input

Output

Sample Input

5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

Sample Output

42

Hint

 题目大意：求一最大生成树

思路：这个题让我快崩溃了，WA了很多次，最后看discuss说有重边。。。改完AC了  疯了。。。

#include<iostream><br /> using namespace std;<br /> struct t<br /> {<br /> int s,e,l;<br /> }tree[2010],h;<br /> int dis[2010][2010];<br /> int main()<br /> {<br /> int n,c,i,j,k,a,b,m;<br /> while(cin>>n>>c&&n)<br /> {<br /> int flag=1;<br /> memset(dis,0,sizeof(dis));<br /> for(i=1;i<=c;i++)<br /> {<br /> cin>>a>>b>>j;<br /> if(dis[a][b]<j)<br /> { dis[a][b]=j; dis[b][a]=j; }<br /> }</p> <p> for(i=1;i<n;i++)<br /> {<br /> tree[i].s=1;<br /> tree[i].e=i+1;<br /> tree[i].l=dis[tree[i].s][tree[i].e];<br /> }<br /> for(i=1;i<n;i++)<br /> {<br /> int min=0;<br /> for(j=i;j<n;j++)<br /> if(tree[j].l>min)<br /> {<br /> min=tree[j].l;<br /> m=j;<br /> }<br /> if(min==0)<br /> { flag=0; break; }<br /> else<br /> {<br /> h=tree[i]; tree[i]=tree[m]; tree[m]=h;<br /> for(j=i+1;j<n;j++)<br /> if(tree[j].l<dis[tree[i].e][tree[j].e])<br /> {<br /> tree[j].s=tree[i].e;<br /> tree[j].l=dis[tree[j].s][tree[j].e];<br /> }<br /> }<br /> }<br /> if(flag)<br /> {<br /> int s=0;<br /> for(i=1;i<n;i++)<br /> s+=tree[i].l;<br /> cout<<s<<endl;<br /> }<br /> else<br /> cout<<"-1"<<endl;<br /> }<br /> return 0;<br /> }