南将军率领着许多部队，它们分别驻扎在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 来源 POJ题目改编 上传者张云聪
模板题目
思路 算法核心思想：在prime求MST的过程中 用数组存储MST里面任意两点间的唯一的路中 权值最大的那条边的权值。最后枚举不在MST里面的边<i,，j>，判断<i，j>的权值 是否 和 MST里面 i 到 j 的最大权值相等，只要有一条边满足就可以说明MST不唯一。（因为我们可以用这条不在MST的边来 代替 在MST的边，这样MST肯定不唯一）
时间复杂度 citys*2
代码：
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<stack> #include<vector> #define inf 0x3f3f3f // 次小生成树 #define M 500+10 using namespace std; int dis[M]; int map[M][M]; int v[M]; //以上的prime算法 都有 int mst[M][M]; //mst中i和j的最大边权值 int inmst[M][M]; //标记这个边是不是在mst中 int pre[M]; // 记录前驱 int citys,roads; void getmap() { for(int i=1;i<=citys;i++) { for(int j=1;j<=citys;j++) { if(i==j) map[i][j]=0; else map[i][j]=map[j][i]=inf; } } for(int i=0;i<roads;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(map[a][b]>c) map[a][b]=map[b][a]=c; } } void solve () { int min,next,sum=0; memset(mst,0,sizeof(mst)); memset(inmst,0,sizeof(inmst)); for(int i=1;i<=citys;i++) { pre[i]=1;// 设置前驱 dis[i]=map[1][i]; v[i]=0; } v[1]=1; for(int u=2;u<=citys;u++) { min=inf; next=-1; for(int j=1;j<=citys;j++) { if(!v[j]&&dis[j]<min) { min=dis[j]; next=j; } } sum+=min; v[next]=1; int fa=pre[next];// 获得前驱 inmst[fa][next]=inmst[next][fa]=1; //在mst中 for (int j=1;j<=citys;j++) { if(v[j]&&j!=next) //mst中的点 mst[j][next]=mst[next][j]=max(mst[fa][j],dis[next]); if(!v[j]&&dis[j]>map[j][next]) { dis[j]=map[j][next]; // 更新距离 pre[j]=next; // 更新前驱 } } } // 判断mst是不是唯一的 for(int i=1;i<=citys;i++) { for(int j=1;j<i;j++) if(map[i][j]!=inf&&!inmst[i][j]) { if(map[i][j]==mst[i][j]) { printf("Yes\n"); return ; } } } printf("No\n"); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&citys,&roads); getmap(); solve(); } return 0; }
