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

次最小生成树

定义：设T是图G的最小生成树，如果T1满足ω(T1)=min{ω(T’)| T’∈Not(T)},则T1是G的次小生成树。

解释：除了最小生成树外，另外一个生成树的权值和最小的生成树，定义为次最小生成树。

经典题目：POJ1679 The Unique MST，对于一张图，判断最小生成树是否惟一。惟一的定义是：不存在第二棵生成树，它的权值与最小生成树的权值相等。w(次最小生成树)!=w(最小生成树)

算法的思路：

在生成最小生成树的时候，判断下一条边的权值是否和这一条边的权值相等，如果相等，则往下判断这两个点的时候和上两个点是否分别连通，若相等，则表示存在另一条边可以生成最小生成树。


krushal+判断

#include<cstdio>

#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
struct Node{int from,to,cost;}es[200010];
int V,E,pre[505];
int find(int x){return x==pre[x]? x : find(pre[x]);}
bool cmp(Node a,Node b){return a.cost < b.cost;}
int main()
{  
    int test;
    scanf("%d",&test);
    while(test--){
        int x,y,z,p=0;;
        scanf("%d%d",&V,&E);
        for(int i = 1; i <= E; i++){
            scanf("%d%d%d",&x,&y,&z); 
            es[p].from = (x > y ? y : x);
            es[p].to = (x > y ? x: y);     
            es[p++].cost=z;
        }               
        sort(es,es+p,cmp);
        for(int i = 1; i <= V; i++)pre[i]=i;
        bool update=false;
        for(int i = 0; i < p; i++){
                int a = find(es[i].from);
                int b = find(es[i].to);
                int c=es[i].cost;
                if(a != b){
                    for(int j = i+1; j < p; j++){                                             
                         if(es[j].cost != c)break;
                         else if(a == find(es[j].from) && b == find(es[j].to)){
                                  update = true;
                                  break;                                  
                         }                              
                    }
                    pre[a] = b;     
                }                              
        }
        if(update)printf("Yes\n");
        else printf("No\n");              
    }
    return 0;
    
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/briup_acmer/article/details/39716855

智能推荐

linux devkmem 源码,linux dev/mem dev/kmem实现访问物理/虚拟内存-程序员宅基地

文章浏览阅读451次。dev/mem: 物理内存的全镜像。可以用来访问物理内存。/dev/kmem: kernel看到的虚拟内存的全镜像。可以用来访问kernel的内容。调试嵌入式Linux内核时，可能需要查看某个内核变量的值。/dev/kmem正好提供了访问内核虚拟内存的途径。现在的内核大都默认禁用了/dev/kmem，打开的方法是在 make menuconfig中选中 device drivers --> ..._dev/mem 源码实现

vxe-table 小众但功能齐全的vue表格组件-程序员宅基地

文章浏览阅读7.1k次，点赞2次，收藏19次。vxe-table，一个小众但功能齐全并支持excel操作的vue表格组件_vxe-table

（开发）bable - es6转码-程序员宅基地

文章浏览阅读62次。参考：http://www.ruanyifeng.com/blog/2016/01/babel.htmlBabelBabel是一个广泛使用的转码器，可以将ES6代码转为ES5代码，从而在现有环境执行// 转码前input.map(item => item + 1);// 转码后input.map(function (item) { return item..._让开发环境支持bable

FPGA 视频处理 FIFO 的典型应用_fpga 频分复用 视频-程序员宅基地

文章浏览阅读2.8k次，点赞6次，收藏29次。摘要：FPGA视频处理FIFO的典型应用，视频输入FIFO的作用，视频输出FIFO的作用，视频数据跨时钟域FIFO，视频缩放FIFO的作用_fpga 频分复用 视频

R语言：设置工作路径为当前文件存储路径_r语言设置工作目录到目标文件夹-程序员宅基地

文章浏览阅读575次。【代码】R语言：设置工作路径为当前文件存储路径。_r语言设置工作目录到目标文件夹

background 线性渐变-程序员宅基地

文章浏览阅读452次。格式：background: linear-gradient(direction, color-stop1, color-stop2, ...);<linear-gradient> = linear-gradient([ [ <angle> | to <side-or-corner>] ,]? &l..._background线性渐变

随便推点

【蓝桥杯省赛真题39】python输出最大的数 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析-程序员宅基地

文章浏览阅读1k次，点赞26次，收藏8次。第十三届蓝桥杯青少年组python编程省赛真题一、题目要求（注：input（）输入函数的括号中不允许添加任何信息）1、编程实现给定一个正整数N，输出正整数N中各数位最大的那个数字。例如:N=132，则输出3。2、输入输出输入描述：只有一行，输入一个正整数N输出描述：只有一行，输出正整数N中各数位最大的那个数字输入样例：

网络协议的三要素-程序员宅基地

文章浏览阅读2.2k次。一个网络协议主要由以下三个要素组成：1.语法数据与控制信息的结构或格式，包括数据的组织方式、编码方式、信号电平的表示方式等。2.语义即需要发出何种控制信息，完成何种动作，以及做出何种应答，以实现数据交换的协调和差错处理。3.时序即事件实现顺序的详细说明，以实现速率匹配和排序。不完整理解：语法表示长什么样，语义表示能干什么，时序表示排序。转载于:https://blog.51cto.com/98..._网络协议三要素csdn

The Log: What every software engineer should know about real-time data's unifying abstraction-程序员宅基地

文章浏览阅读153次。主要的思想，将所有的系统都可以看作两部分，真正的数据log系统和各种各样的query engine所有的一致性由log系统来保证，其他各种query engine不需要考虑一致性，安全性，只需要不停的从log系统来同步数据，如果数据丢失或crash可以从log系统replay来恢复可以看出kafka系统在linkedin中的重要地位，不光是d..._the log: what every software engineer should know about real-time data's uni

《伟大是熬出来的》冯仑与年轻人闲话人生之一-程序员宅基地

文章浏览阅读746次。伟大是熬出来的　　目录　　前言　　引言 时间熬成伟大：领导者要像狼一样坚忍 　　第一章 内圣外王——领导者的心态修炼　　1. 天纵英才的自信心　　2. 上天揽月的企图心　　3. 誓不回头的决心　　4. 宠辱不惊的平常心　　5. 换位思考的同理心　　6. 激情四射的热心　　第二章 日清日高——领导者的高效能修炼　　7. 积极主动，想到做到　　8. 合理掌控自己的时间和生命　　9. 制定目标，马..._当狼拖着受伤的右腿逃生时,右腿会成为前进的阻碍,它会毫不犹豫撕咬断自己的腿, 以

有源光缆AOC知识百科汇总-程序员宅基地

文章浏览阅读285次。在当今的大数据时代，人们对高速度和高带宽的需求越来越大，迫切希望有一种新型产品来作为高性能计算和数据中心的主要传输媒质，所以有源光缆（AOC）在这种环境下诞生了。有源光缆究竟是什么呢？应用在哪些领域，有什么优势呢？易天将为您解答！有源光缆（Active Optical Cables，简称AOC）是两端装有光收发器件的光纤线缆，主要构成部件分为光路和电路两部分。作为一种高性能计..._aoc 光缆

浏览器代理服务器自动配置脚本设置方法-程序员宅基地

文章浏览阅读2.2k次。在“桌面”上按快捷键“Ctrl+R”，调出“运行”窗口。接着，在“打开”后的输入框中输入“Gpedit.msc”。并按“确定”按钮。如下图 找到“用户配置”下的“Windows设置”下的“Internet Explorer 维护”的“连接”，双击选择“自动浏览器配置”。如下图 选择“自动启动配置”，并在下面的“自动代理URL”中填写相应的PAC文件地址。如下..._設置proxy腳本

推荐文章

热门文章

相关标签