问题 H: Vegetable and Road again
时间限制: 1 Sec 内存限制: 128 MB
提交: 19 解决: 8
题目描述
修路的方案终于确定了。市政府要求任意两个公园之间都必须实现公路交通（并不一定有直接公路连接，间接公路相连也可以）。但是考虑到经济成本，市政府希望钱花的越少越好。
你能帮助Vegetable找到给出的修路方案所需的最少花费吗？
输入
有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<cstdio>
#include<algorithm>
using namespace std; const int maxn = ; int f[maxn]; struct edge
{
int from;
int to;
int cost;
friend bool operator < (edge a,edge b)
{
return a.cost < b.cost;
}
}e[maxn]; void ufs(int n)
{
for(int i = ; i <= n; i++)
f[i] = i;
} int findd(int x)
{
if(f[x] == x)
return x;
else return findd(f[x]);
} void merger(int x,int y)
{
int fx = findd(x);
int fy = findd(y);
if(fx != fy)
f[fy] = fx;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
ufs(n);
int cnt = ;
for(int i = ; i < m; i++)
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].cost);
sort(e,e + m);
for(int i = ; i < m; i++)
{
if(findd(e[i].from) != findd(e[i].to))
{
merger(e[i].from,e[i].to);
cnt += e[i].cost;
}
}
int flag = ;
for(int i = ; i < n; i++)
{
if(findd(f[i]) != findd(f[i + ]))
{
flag = ;
printf("Wrong\n");
break;
}
}
if(flag)
printf("%d\n",cnt);
}
return ;
}