描述
南将军率领着许多部队，它们分别驻扎在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
题目大意：将N个点连通的最短路径是否唯一。
题目思路：求最短路径求出最小生成树即可，最短路是否唯一，只要判断次小生成树的值是否和最小生成树的值相等即可。求次小生成树的方法，求出最小生成树后，最小生成树中所用到的边，依此枚举取掉其中一条边所能得到的最小生成树，(例如，一共有边1，2，3，4，5。最小生成树用到边1，2，3。那么依此算出(2，3，4，5) (1，3，4，5) (1，2，4，5) 这三种情况的最小生成树。)这些最小生成树中的最小值为次小生成树，在建树完成后，要判断这n个结点是否连通。
#include<cstdio>
#include<algorithm>
#define N 505
using namespace std;
int p[N],n,m,min1,min2,T;
int vis[N*N];
struct E{int a,b,dis;int vis;
}e[N*N];bool cmp(E e1,E e2){return e1.dis<e2.dis;
}int find(int x){return p[x] == x ? x : p[x] = find(p[x]);
}int Kruscal(int u){int ans = 0;for(int i=0 ;i<m ;i++){if(u!=i){int fx = find(e[i].a);int fy = find(e[i].b);if(fx!=fy){ans += e[i].dis;p[fx] = fy;} }}int father = find(1);for(int i=2 ;i<=n ;i++){if(find(i)!=father)ans = -1;}return ans;
}void init(){for(int i=0 ;i<=n ;i++) p[i] = i;
}int main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0 ;i<m ;i++){scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].dis);e[i].vis = 0; }int flag = 1;min1 = min2 = 0;//求最小生成树 init();sort(e,e+m,cmp);for(int i=0 ;i<m ;i++){int fx = find(e[i].a);int fy = find(e[i].b);if(fx!=fy){e[i].vis = 1;p[fx] = fy;min1 += e[i].dis;}}//求次小生成树 for(int i=0 ;i<m ;i++){if(e[i].vis==1){init();min2 = Kruscal(i);}if(min2==min1){flag = 0;break;}}if(flag)puts("No");else puts("Yes");}return 0;
}