首页 > 代码库 > nyoj 118 修路方案
nyoj 118 修路方案
修路方案
时间限制:3000 ms | 内存限制:65535 KB
难度:5
描述
南将军率领着许多部队,它们分别驻扎在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<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 修路方案
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。