POJ 1679 The Unique MST(次短生成树)
发布日期:2021-08-12 02:36:17 浏览次数:4 分类:技术文章

本文共 1976 字,大约阅读时间需要 6 分钟。

Language:Default
The Unique MST
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 29098   Accepted: 10404

Description

Given a connected undirected graph, tell if its minimum spanning tree is unique. 
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties: 
1. V' = V. 
2. T is connected and acyclic. 
Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'. 

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.

Sample Input

23 31 2 12 3 23 1 34 41 2 22 3 23 4 24 1 2

Sample Output

3Not Unique!

思路:找有没有次短生成树,先找出最小生成树,再把每条边替换,是否与最小生成树相同

#include
#include
#include
#define MAXN 201struct node { int x,y; int val;};node a[MAXN*MAXN];int fa[MAXN],n,t,m,num[MAXN*MAXN],dis;bool flag;using namespace std;inline void read(int&x) { x=0;int f=1;char c=getchar(); while(c>'9'||c<'0') {
if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();} x=x*f;}inline int find(int x) { if(x==fa[x]) return x; else return fa[x]=find(fa[x]);}inline bool cmp(node x,node y) { return x.val
View Code

 

转载于:https://www.cnblogs.com/whistle13326/p/6366291.html

转载地址:https://blog.csdn.net/weixin_30642561/article/details/97266113 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:wx.request 获取不到post传递的值
下一篇:指定周转对应日期

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月12日 10时38分24秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python中func自定义函数_Python函数之自定义函数&作用域&闭包 2019-04-21
wget连接指定端口_端口通不通 telnet wget ssh 2019-04-21
eureka 调用服务_Spring Cloud微服务架构从入门到会用(二)—服务注册中心Eureka... 2019-04-21
easyexcel 工具类_问了个在阿里的同学,他们常用的15款开发者工具! 2019-04-21
mysql统计结果大于0时返回true_mysql表查询练习 2019-04-21
php mysql查询count_php – 如何使这个MySQL Count查询更有效? 2019-04-21
mysql登录15046_ASMCMD命令拷贝文件报错ORA-15046 (转) 2019-04-21
mac 设置mysql登录快捷键_mac安装mysql中设置密码遇到的问题和设置快捷命令打开mysql... 2019-04-21
mysql5.7中文匹配度 match_深度解析MySQL 5.7之中文全文检索 2019-04-21
node mysql 事件循环_nodejs的事件循环简单理解 2019-04-21
python 百分比 图_python图元素的百分比格式 2019-04-21
对方正在输入 java_pom.xml · 对方正在输入.../java2flyweb - Gitee.com 2019-04-21
java参数判断_[Java教程]判断参数是否符合要求的一个类 2019-04-21
java基础入门第二版课第八章_Java基础入门-第八章-15 2019-04-21
四线温度传感器怎么接线图_实用!西门子S71200系列PLC全套接线图 2019-04-21
配置idea自带的tomcat_Tomcat下载安装并部署到IDEA的教程(附带idea两种热部署设置方法)... 2019-04-21
bwl老二吃嘲讽吗_魔兽世界怀旧服bwl老三吃冲击波减不减仇恨? 2019-04-21
es 默认排序字段_Elasticsearch sort排序子句 2019-04-21
代码设置margintop_HTML5如何解决margin-top的塌陷问题(附代码) 2019-04-21
java显示一个钟表_java实现时钟效果 2019-04-21