POJ 1679:The Unique MST(次小生成树&&Kruskal)[通俗易懂]

POJ 1679:The Unique MST(次小生成树&&Kruskal)

大家好,又见面了,我是全栈君。


Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 19941   Accepted: 6999

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

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

Sample Output

3
Not Unique!

这道题就是要你推断是否为唯一的最小生成树。。

这也是我第一道次小生成树的题。。那个PDF资料真是太好了。。我用的是Kruskal。。


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

const int max1 = 105;
const int max2 = 10005;

struct node
{
    int u, v, w;//边的顶点以及权值
    int r;//用于记录边的序号
    int used;//用于记录边是否被使用过
}edge[max2];//边的数组

int parent[max1];//顶点i所在集合相应树中的根节点
int n, m;//顶点数,边的个数
int cas;

void start()//初始化
{
    for(int i=1; i<=n; i++)
        parent[i] = i;
}

int find (int x)//查找并返回节点x所属集合的根节点
{
    return parent[x] == x ?

x : parent[x] = find ( parent[x] );}bool cmp ( node a, node b )//按权值从小到大排序{ return a.w < b.w;}int Kruskal()//第一次求最小生成树{ sort( edge+1, edge+m+1, cmp ); int ans = 0; for(int i=1; i<=m; i++) { int e = edge[i].r; int x = find( edge[i].u ); int y = find( edge[i].v ); if( x!=y ) { parent[y] = x; ans += edge[i].w; edge[e].used = 1; } } return ans;}int Kruskal_again(int tt)//求次小生成树{ sort( edge+1, edge+m+1, cmp ); int ans = 0; for(int i=1; i<=m; i++) { if( tt==edge[i].r ) continue; int x = find( edge[i].u ); int y = find( edge[i].v ); if( x!=y ) { parent[y] = x; ans += edge[i].w; } } return ans;}bool judge()//推断是否能就得最小生成树,即看是否有孤立的点{ for(int i=1; i<=n; i++) if( find(i) != find(1) ) return false; return true;}int main(){ scanf("%d", &cas); while( cas-- ) { scanf("%d%d", &n, &m); start(); for(int i=1; i<=m; i++) { scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); edge[i].used = 0; edge[i].r = i; } int flag = 0; int ans1 = Kruskal(); for(int i=1; i<=m; i++)//一一枚举求最小生成树。。 { if( !edge[i].used ) continue; start(); int ans2 = Kruskal_again(i);//求除去此边的最小生成树 if( ans1 == ans2 && judge() ) { flag = 1;//标记结论 break; } } if( flag ) printf("Not Unique!\n"); else printf("%d\n", ans1); } return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115989.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 尺度空间家具_空间尺度分析

    尺度空间家具_空间尺度分析尺度空间的基本思想:在视觉信息(图像信息)处理模型中引入一个被视为尺度的参数,通过连续变化尺度参数获得不同尺度下视觉处理信息,然后综合这些信息以深入地挖掘图像的本质特征。尺度空间方法将传统的单尺度视觉信息处理技术纳入尺度不断变化的动态构架中,因此更容易获得图像的本质特征。尺度空间生成的目的是模拟图像数据的多尺度特征。尺度空间理论是通过对原始图像进行尺度变换,获得图像多尺度下的尺度空间表示

  • OpenCV学习笔记(30)KAZE 算法原理与源码分析(四)KAZE特征的性能分析与比较

    OpenCV学习笔记(30)KAZE 算法原理与源码分析(四)KAZE特征的性能分析与比较KAZE系列笔记:1. OpenCV学习笔记(27)KAZE算法原理与源码分析(一)非线性扩散滤波2. OpenCV学习笔记(28)KAZE算法原理与源码分析(二)非线性尺度空间构建3. OpenCV学习笔记(29)KAZE算法原理与源码分析(三)特征检测与描述4. OpenCV学习笔记(30)KAZE算法原理与源码分析(四)KAZE特征的性能分析与比较5. OpenCV学习笔记

  • android之Activity.startManagingCursor方法详解

    在使用数据库操作查询数据后,如果是在Activity里面处理,那么很可能就会用到startManagingCursor()方法,在这里讲一下它的作用和使用注意事项.调用这个方法,就是将获得的Cursor对象交与Activity 来管理,这样Cursor对象的生命周期便能与当前的Activity自动同步,省去了自己管理Cursor。看下文档里的注释This method allows

  • route命令的使用详解[通俗易懂]

    route命令的使用详解[通俗易懂]Linux系统的route命令用于显示和操作IP路由表(show / manipulate the IP routing table)。要实现两个不同的子网之间的通信,需要一台连接两个网络的路由器,或者同时位于两个网络的网关来实现。在Linux系统中,设置路由通常是为了解决以下问题:该Linux系统在一个局域网中,局域网中有一个网关,能够让机器访问Internet,那么就需要将这台机器的IP地址设…

  • windows10 bat命令获取日期时间「建议收藏」

    windows10 bat命令获取日期时间「建议收藏」系统版本win10英文OSWindowsEdition:Windows10ProSettings-Language:English(UnitedStates)获取日期命令完整的日期:date(输出如下图)裁剪方法:echo%date:~起点位,数据长度%【英文版】对date进行裁剪获取年月日:年:echo%date:~6,4%月:echo%date:~0,2%日:echo%date:~3,2%年月日:%date:~6,4%-%date:~0,2%-%date

  • linux下编译jrtplib-3.9.1

    一、下载jrtplib、jthreadjrtplib:http://research.edm.uhasselt.be/jori/jrtplib/jrtplib-3.9.1.zipjthread:http://research.edm.uhasselt.be/jori/jthread/jthread-1.3.1.zipCMake:https://cmake.org/downl

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号