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

智能推荐

软件测试流程包括哪些内容?测试方法有哪些?_测试过程管理中包含哪些过程-程序员宅基地

文章浏览阅读2.9k次,点赞8次,收藏14次。测试主要做什么?这完全都体现在测试流程中,同时测试流程是面试问题中出现频率最高的,这不仅是因为测试流程很重要,而是在面试过程中这短短的半小时到一个小时的时间,通过测试流程就可以判断出应聘者是否合适,故在测试流程中包含了测试工作的核心内容,例如需求分析,测试用例的设计,测试执行,缺陷等重要的过程。..._测试过程管理中包含哪些过程

政府数字化政务的人工智能与机器学习应用:如何提高政府工作效率-程序员宅基地

文章浏览阅读870次,点赞16次,收藏19次。1.背景介绍政府数字化政务是指政府利用数字技术、互联网、大数据、人工智能等新技术手段,对政府政务进行数字化改革,提高政府工作效率,提升政府服务质量的过程。随着人工智能(AI)和机器学习(ML)技术的快速发展,政府数字化政务中的人工智能与机器学习应用也逐渐成为政府改革的重要内容。政府数字化政务的人工智能与机器学习应用涉及多个领域,包括政策决策、政府服务、公共安全、社会治理等。在这些领域,人工...

ssm+mysql+微信小程序考研刷题平台_mysql刷题软件-程序员宅基地

文章浏览阅读219次,点赞2次,收藏4次。系统主要的用户为用户、管理员,他们的具体权限如下:用户:用户登录后可以对管理员上传的学习视频进行学习。用户可以选择题型进行练习。用户选择小程序提供的考研科目进行相关训练。用户可以进行水平测试,并且查看相关成绩用户可以进行错题集的整理管理员:管理员登录后可管理个人基本信息管理员登录后可管理个人基本信息管理员可以上传、发布考研的相关例题及其分析,并对题型进行管理管理员可以进行查看、搜索考研题目及错题情况。_mysql刷题软件

根据java代码描绘uml类图_Myeclipse8.5下JAVA代码导成UML类图-程序员宅基地

文章浏览阅读1.4k次。myelipse里有UML1和UML2两种方式,UML2功能更强大,但是两者生成过程差别不大1.建立Test工程,如下图,uml包存放uml类图package com.zz.domain;public class User {private int id;private String name;public int getId() {return id;}public void setId(int..._根据以下java代码画出类图

Flume自定义拦截器-程序员宅基地

文章浏览阅读174次。需求:一个topic包含很多个表信息,需要自动根据json字符串中的字段来写入到hive不同的表对应的路径中。发送到Kafka中的数据原本最外层原本没有pkDay和project,只有data和name。因为担心data里面会空值,所以根同事商量,让他们在最外层添加了project和pkDay字段。pkDay字段用于表的自动分区,proejct和name合起来用于自动拼接hive表的名称为 ..._flume拦截器自定义开发 kafka

java同时输入不同类型数据,Java Spring中同时访问多种不同数据库-程序员宅基地

文章浏览阅读380次。原标题:Java Spring中同时访问多种不同数据库 多样的工作要求,可以使用不同的工作方法,只要能获得结果,就不会徒劳。开发企业应用时我们常常遇到要同时访问多种不同数据库的问题,有时是必须把数据归档到某种数据仓库中,有时是要把数据变更推送到第三方数据库中。使用Spring框架时,使用单一数据库是非常容易的,但如果要同时访问多个数据库的话事件就变得复杂多了。本文以在Spring框架下开发一个Sp..._根据输入的不同连接不同的数据库

随便推点

EFT试验复位案例分析_eft电路图-程序员宅基地

文章浏览阅读3.6k次,点赞9次,收藏25次。本案例描述了晶振屏蔽以及开关电源变压器屏蔽对系统稳定工作的影响, 硬件设计时应考虑。_eft电路图

MR21更改价格_mr21 对于物料 zba89121 存在一个当前或未来标准价格-程序员宅基地

文章浏览阅读1.1k次。对于物料价格的更改,可以采取不同的手段:首先,我们来介绍MR21的方式。 需要说明的是,如果要对某一产品进行价格修改,必须满足的前提条件是: ■ 1、必须对价格生效的物料期间与对应会计期间进行开启; ■ 2、该产品在该物料期间未发生物料移动。执行MR21,例如更改物料1180051689的价格为20000元,系统提示“对于物料1180051689 存在一个当前或未来标准价格”,这是因为已经对该..._mr21 对于物料 zba89121 存在一个当前或未来标准价格

联想启天m420刷bios_联想启天M420台式机怎么装win7系统(完美解决usb)-程序员宅基地

文章浏览阅读7.4k次,点赞3次,收藏13次。[文章导读]联想启天M420是一款商用台式电脑,预装的是win10系统,用户还是喜欢win7系统,该台式机采用的intel 8代i5 8500CPU,在安装安装win7时有很多问题,在安装win7时要在BIOS中“关闭安全启动”和“开启兼容模式”,并且安装过程中usb不能使用,要采用联想win7新机型安装,且默认采用的uefi+gpt模式,要改成legacy+mbr引导,那么联想启天M420台式电..._启天m420刷bios

冗余数据一致性,到底如何保证?-程序员宅基地

文章浏览阅读2.7k次,点赞2次,收藏9次。一,为什么要冗余数据互联网数据量很大的业务场景,往往数据库需要进行水平切分来降低单库数据量。水平切分会有一个patition key,通过patition key的查询能..._保证冗余性

java 打包插件-程序员宅基地

文章浏览阅读88次。是时候闭环Java应用了 原创 2016-08-16 张开涛 你曾经因为部署/上线而痛苦吗?你曾经因为要去运维那改配置而烦恼吗?在我接触过的一些部署/上线方式中,曾碰到过以下一些问题:1、程序代码和依赖都是人工上传到服务器,不是通过工具进行部署和发布;2、目录结构没有规范,jar启动时通过-classpath任意指定;3、fat jar,把程序代码、配置文件和依赖jar都打包到一个jar中,改配置..._那么需要把上面的defaultjavatyperesolver类打包到插件中

VS2015,Microsoft Visual Studio 2005,SourceInsight4.0使用经验,Visual AssistX番茄助手的安装与基本使用9_番茄助手颜色-程序员宅基地

文章浏览阅读909次。1.得下载一个番茄插件,按alt+g才可以有函数跳转功能。2.不安装番茄插件,按F12也可以有跳转功能。3.进公司的VS工程是D:\sync\build\win路径,.sln才是打开工程的方式,一个是VS2005打开的,一个是VS2013打开的。4.公司库里的线程接口,在CmThreadManager.h 里,这个里面是我们的线程库,可以直接拿来用。CreateUserTaskThre..._番茄助手颜色

推荐文章

热门文章

相关标签