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

智能推荐

FX3/CX3 JLINK 调试_ezusbsuite_qsg.pdf-程序员宅基地

文章浏览阅读2.1k次。FX3 JLINK调试是一个有些麻烦的事情，经常有些莫名其妙的问题。 设置参见 c:\Program Files (x86)\Cypress\EZ-USB FX3 SDK\1.3\doc\firmware 下的 EzUsbSuite_UG.pdf 文档。 常见问题： 1.装了多个版本的jlink，使用了未注册或不适当的版本 选择一个正确的版本。JLinkARM_V408l，JLinkA_ezusbsuite_qsg.pdf

用openGL+QT简单实现二进制stl文件读取显示并通过鼠标旋转缩放_qopengl如何鼠标控制旋转-程序员宅基地

文章浏览阅读2.6k次。** 本文仅通过用openGL+QT简单实现二进制stl文件读取显示并通过鼠标旋转缩放， 是比较入门的级别，由于个人能力有限，新手级别，所以未能施加光影灯光等操作， 未能让显示的stl文件更加真实。****效果图：**1. main.cpp```cpp#include "widget.h"#include <QApplication>int main(int argc, char *argv[]){ QApplication a(argc, argv); _qopengl如何鼠标控制旋转

刘焕勇&王昊奋｜ChatGPT对知识图谱的影响讨论实录-程序员宅基地

文章浏览阅读943次，点赞22次，收藏19次。以大规模预训练语言模型为基础的chatgpt成功出圈，在近几日已经给人工智能板块带来了多次涨停，这足够说明这一风口的到来。而作为曾经的风口“知识图谱”而言，如何找到其与chatgpt之间的区别，找好自身的定位显得尤为重要。形式化知识和参数化知识在表现形式上一直都是大家考虑的问题，两种技术都应该有自己的定位与价值所在。知识图谱构建往往是抽取式的，而且往往包含一系列知识冲突检测、消解过程，整个过程都能溯源。以这样的知识作为输入，能在相当程度上解决当前ChatGPT的事实谬误问题，并具有可解释性。

如何实现tomcat的热部署_tomcat热部署-程序员宅基地

文章浏览阅读1.3k次。最重要的一点，一定是degbug的方式启动，不然热部署不会生效，注意，注意！_tomcat热部署

用HTML5做一个个人网站，此文仅展示个人主页界面。内附源代码下载地址_个人主页源码-程序员宅基地

文章浏览阅读10w+次，点赞56次，收藏482次。html5 ，用css去修饰自己的个人主页代码如下：&lt;!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;&lt;html xmlns="http://www.w3.org/1999/xh..._个人主页源码

程序员公开上班摸鱼神器！有了它，老板都不好意思打扰你！-程序员宅基地

文章浏览阅读201次。开发者（KaiFaX）面向全栈工程师的开发者专注于前端、Java/Python/Go/PHP的技术社区来源：开源最前线链接：https://github.com/svenstaro/gen..._程序员怎么上班摸鱼

随便推点

UG\NX二次开发 改变Block UI界面的尺寸_ug二次开发 调整 对话框大小-程序员宅基地

文章浏览阅读1.3k次。改变Block UI界面的尺寸_ug二次开发 调整 对话框大小

基于深度学习的股票预测（完整版，有代码）_基于深度学习的股票操纵识别研究python代码-程序员宅基地

文章浏览阅读1.3w次，点赞18次，收藏291次。基于深度学习的股票预测数据获取数据转换LSTM模型搭建训练模型预测结果数据获取采用tushare的数据接口（不知道tushare的筒子们自行百度一下，简而言之其免费提供各类金融数据 , 助力智能投资与创新型投资。）python可以直接使用pip安装tushare!pip install tushareCollecting tushare Downloading https://files.pythonhosted.org/packages/17/76/dc6784a1c07ec040e74_基于深度学习的股票操纵识别研究python代码

中科网威工业级防火墙通过电力行业测评_电力行业防火墙有哪些-程序员宅基地

文章浏览阅读2k次。【IT168 厂商动态】 近日，北京中科网威(NETPOWER)工业级防火墙通过了中国电力工业电力设备及仪表质量检验测试中心(厂站自动化及远动)测试，并成为中国首家通过电力协议访问控制专业测评的工业级防火墙生产厂商。 　　北京中科网威(NETPOWER)工业级防火墙专为工业及恶劣环境下的网络安全需求而设计，它采用了非X86的高可靠嵌入式处理器并采用无风扇设计，整机功耗不到22W，具备极_电力行业防火墙有哪些

第十三周 ——项目二 “二叉树排序树中查找的路径”-程序员宅基地

文章浏览阅读206次。/*烟台大学计算机学院 作者:董玉祥 完成日期: 2017 12 3 问题描述：二叉树排序树中查找的路径 */#include #include #define MaxSize 100typedef int KeyType; //定义关键字类型typedef char InfoType;typedef struct node

C语言基础 -- scanf函数的返回值及其应用_c语言ignoring return value-程序员宅基地

文章浏览阅读775次。当时老师一定会告诉你，这个一个"warning"的报警，可以不用管它，也确实如此。不过，这条报警信息我们至少可以知道一点，就是scanf函数调用完之后是有一个返回值的，下面我们就要对scanf返回值进行详细的讨论。并给出在编程时利用scanf的返回值可以实现的一些功能。_c语言ignoring return value

数字医疗时代的数据安全如何保障？_数字医疗服务保障方案-程序员宅基地

文章浏览阅读9.6k次。十四五规划下，数据安全成为国家、社会发展面临的重要议题，《数据安全法》《个人信息保护法》《关键信息基础设施安全保护条例》已陆续施行。如何做好“数据安全建设”是数字时代的必答题。_数字医疗服务保障方案

推荐文章

热门文章

相关标签