enter qsort highlight space logs stdio.h can void
时间限制:3000 ms | 内存限制:65535 KB
难度:5
描述
南将军率领着许多部队,它们分别驻扎在 N 个不同的城市里,这些城市分别编号 1~N,由于交通不太便利,南将军准备修路。
现在已经知道哪些城市之间可以修路,如果修路,花费是多少。
现在,军师小工已经找到了一种修路的方案,能够使各个城市都联通起来,而且花费最少。
但是,南将军说,这个修路方案所拼成的图案很不吉利,想让小工计算一下是否存在另外一种方案花费和刚才的方案一样,现在你来帮小工写一个程序算一下吧。
输入
第一行输入一个整数 T(1 每组测试数据的第一行是两个整数 V,E,(3 随后的 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<stdio.h>
- #include<string>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define MaxV 510
- #define MaxE 200005
- struct Edge
- {
- int x,y,dis;
- };
- Edge edge[MaxE],edge1[MaxE]; //分别是边数组 最小生成树中的边数组
- int father[MaxV],Num[MaxV],num,dex,dey; //并查集 num统计生成树边的条数 dex dey指枚举删除边的x,y坐标
- void Init(int V) //并查集初始化,单个元素自成集合
- {
- for(int i=1;i<=V;i++)
- {
- father[i]=i;
- Num[i]=1;
- }
- }
- int findfather(int x) //寻找父结点,可以压缩路径。。
- {
- for(x;x!=father[x];x=father[x]) ;
- return father[x];
- }
- void Union(int x,int y)
- {
- int t1,t2;
- t1=findfather(x);
- t2=findfather(y);
- if(Num[t1]>Num[t2])
- {
- father[t2]=t1;
- Num[t1]+=Num[t2];
- }
- else
- {
- father[t1]=t2;
- Num[t2]+=Num[t1];
- }
- }
- int comp(const void* p1,const void* p2)
- {
- return (*(Edge*)p1).dis>(*(Edge*)p2).dis;
- }
- int Krusual(int V,int E)
- {
- int sum=0;
- for(int i=1;i<=E;i++)
- {
- if(findfather(edge[i].x)!=findfather(edge[i].y))
- {
- sum+=edge[i].dis;
- Union(edge[i].x,edge[i].y);
- edge1[++num]=edge[i];//将生成树的边加入到edge1中
- }
- }
- return sum;
- }
- int AKrusual(int V,int E)
- {
- Init(V);
- int sum=0;
- qsort(edge+1,E,sizeof(edge[1]),comp);
- int k;
- for(k=1;k<=E;++k)
- {
- if(findfather(edge[k].x)!=findfather(edge[k].y))
- {
- if(edge[k].x==dex&&edge[k].y==dey)
- {continue;}
- if(edge[k].x==dey&&edge[k].x==dex)
- {continue;}
- sum+=edge[k].dis;
- Union(edge[k].x,edge[k].y);
- }
- }
- return sum;
- }
- bool Judge(int V) //判断图是否连通,不连通则无法构造最小生成树
- {
- for(int m=1;m<=V-1;++m)
- if(findfather(m)!=findfather(m+1))
- return false;
- return true;
- }
- int main()
- {
- int test,j,V,E;
- scanf("%d",&test);
- while(test--)
- {
- scanf("%d%d",&V,&E);
- num=0;
- for(j=1;j<=E;++j)
- {
- scanf("%d%d%d",&edge[j].x,&edge[j].y,&edge[j].dis);
- }
- qsort(edge+1,E,sizeof(edge[1]),comp);
- Init(V);
- int sum=Krusual(V,E);
- int M=1000,temp;
- for(int q=1;q<=num;++q)
- {
- dex=edge1[q].x;
- dey=edge1[q].y;
- temp=AKrusual(V,E);
- if(temp<M&&Judge(V))
- M=temp;
- if(M==sum) break;
- }
- if(M==sum) printf("Yes\n");
- else printf("No\n");
- }
- }
nyoj 118 修路方案
来源: http://www.bubuko.com/infodetail-2129087.html