算法：次小生成树
描述
南将军率领着许多部队，它们分别驻扎在N个不同的城市里，这些城市分别编号1~N，由于交通不太便利，南将军准备修路。
现在已经知道哪些城市之间可以修路，如果修路，花费是多少。
现在，军师小工已经找到了一种修路的方案，能够使各个城市都联通起来，而且花费最少。
但是，南将军说，这个修路方案所拼成的图案很不吉利，想让小工计算一下是否存在另外一种方案花费和刚才的方案一样，现在你来帮小工写一个程序算一下吧。
- 输入
- 第一行输入一个整数T(1<T<20)，表示测试数据的组数
每组测试数据的第一行是两个整数V,E，(3<V<500,10<E<200000)分别表示城市的个数和城市之间路的条数。数据保证所有的城市都有路相连。
随后的E行，每行有三个数字A B L，表示A号城市与B号城市之间修路花费为L。 - 输出
- 对于每组测试数据输出Yes或No（如果存在两种以上的最小花费方案则输出Yes,如果最小花费的方案只有一种，则输出No)
- 样例输入
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2- 样例输出
No
Yes 代码：#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <string>
#include <stdio.h>
using namespace std;
int pre[],m,n;
struct dot
{
int x,y,val,step;
} node[];
int cmp(dot a1,dot a2)
{return a1.val<a2.val;}
void inct()
{
for(int i=;i<=;i++)
pre[i]=i;
}
int find(int ax)
{
while(ax!=pre[ax]) ax=pre[ax];
return ax;
}
int check(int w)
{
int sum=;
for(int i=;i<m;i++)
{
if(i!=w)
{
int fx=find(node[i].x);
int fy=find(node[i].y);
if(fx!=fy)
{
sum+=node[i].val;
pre[fy]=fx;
}
}
}
int s=find();
for(int i=;i<=n;i++)
if(find(i)!=s) return -;
return sum;
}
int main()
{
int i,j,k,q,p,T,mmin;
cin>>T;
while(T--)
{
inct();
cin>>n>>m;
for(i=;i<m;i++)
{
cin>>node[i].x>>node[i].y>>node[i].val;
node[i].step=;
}
sort(node,node+m,cmp);
mmin=;
for(i=;i<m;i++)
{
int fx=find(node[i].x);
int fy=find(node[i].y);
if(fx!=fy)
{
mmin+=node[i].val;
pre[fy]=fx;
node[i].step=;//标记此边最小生成树用过；
}
}
int flag=;
for(i=;i<m;i++)
{
if(node[i].step)
{
inct();
int ans=check(i);
if(ans==mmin)
{
flag=;
break;
}
}
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return ;
}