NYOJ

    xiaoxiao2021-03-25  44

    修路方案 时间限制: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 <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; int father[510]; int n,m; struct Edge { int a; int b; int w; int f; }s[200010]; void init() { int i; for(i=1;i<=n;i++) { father[i] = i; } } int cmp(Edge a,Edge b)//从小到大排序 { return a.w<b.w; } int find(int x) { if(x==father[x]) { return x; } else { return father[x] = find(father[x]); } } int fun(int x) { int i; int sum = 0; for(i=0;i<m;i++) { if(i!=x) //去掉之前最小生成树的一条边, { int fa = find(s[i].a); int fb = find(s[i].b); if(fa!=fb) { father[fa] = fb; sum+=s[i].w; } } } int s = find(1);//判断全部的点是不是已经全部连进去 for(i=2;i<=n;i++) { if(father[i]!=s) { return -1; } } return sum; } int main() { int T; scanf("%d",&T); int sum; while(T--) { scanf("%d%d",&n,&m); int i,j; init(); for(i=0;i<m;i++) { scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].w); s[i].f = 0; } sort(s,s+m,cmp); sum = 0; for(i=0;i<m;i++)//先求出最小生成树 { int fa = find(s[i].a); int fb = find(s[i].b); if(fa!=fb) { father[fa] = fb; s[i].f = 1; sum += s[i].w; //找到最小生成树的值 } } int count = 0 ; bool flag = false; for(i=0;i<m;i++)//枚举所有的边 { if(s[i].f) //每次排除一条边 { init(); if(sum==fun(i)) { flag = true; break; } } if(flag) break; } if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-50282.html

    最新回复(0)