hpu oj 老王修马路

修路的方案终于确定了。市政府要求任意两个公园之间都必须实现公路交通（并不一定有直接公路连接，间接公路相连也可以）。但是考虑到经济成本，市政府希望钱花的越少越好。你能帮助老王找到给出的修路方案所需的最少花费吗？

有T组测试数据。每组包含一组N(0<n<=100)和M，N表示有N个公园，M表示这N个公园间的M条路。接下来给出M行，每行包括A，B, C。表示A和B之间修公路需要花费C元。

若给出的方案可行，输出该方案最小需要的花费，若给出的方案不可行，输出Wrong。

1
4 3
1 2 1
2 3 2
3 4 3

6

#include<stdio.h> 
#include<algorithm> 
#define MAX 1000 
using namespace std; 
struct node { 
int v; 
int u; 
int cost; 
} g[MAX]; 
int par[MAX]; 
int find(int x) { 
return x==par[x]? x:find(par[x]); 
} 
void unite(int x,int y) { 
int fx=find(x); 
int fy=find(y); 
if(fx!=fy) 
par[fx]=fy; 
} 
bool cmp(node x,node y) { 
return x.cost<y.cost; 
} 
bool same(int x,int y) { 
return find(x)==find(y); 
} 
int main() { 
int t,m,n; 
scanf("%d",&t); 
while(t--) { 
scanf("%d%d",&n,&m); 
for(int i=0; i<=n; i++) par[i]=i; 
for(int i=0; i<m; i++) 
scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].cost); 
sort(g,g+m,cmp); 
int ans=0; 
int val=0; 
for(int i=0; i<m; i++) { 
if(!same(g[i].v,g[i].u)) { 
unite(g[i].v,g[i].u); 
val+=g[i].cost; 
} 
} 
for(int i=1; i<=n; i++) { 
int s=find(i); 
if(s==i) { 
ans++; 
} 
} 
if(ans==1)  printf("%d\n",val); 
else printf("Wrong\n"); 
} 
return 0; 
}