The Unique MST
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 20786 | Accepted: 7314 |
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'.
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!
题意:
给出 T 组数组,每组数据给出 N, M,代表有有 N 个节点, M 条无向边,问是否有唯一的一颗最小生成树,有则输出这个值,没有则输出 Not Unique!
思路:
次小生成树。先用 Prim 算法算出最小生成树,记录最小生成树的边是什么,然后枚举生成树的边,一条条删去,删去后再求一遍生成树,如果所构成的图连通且这个值与原来最小生成树的值相等则输出 Not Unique,如果没有则说明唯一。注意每次都要判断是否连通。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef struct { int a, b, num; } node; node no[200005]; int root[505], path[505]; int n, m, cnt, sum; void init() { for (int i = 1; i <= n; ++i) root[i] = i; } int Find (int x) { return x == root[x] ? x : root[x] = Find(root[x]); } bool cmp (node a, node b) { return a.num < b.num; } bool test() { int num = 0; for (int i = 1; i <= n; ++i) { if (root[i] == i) ++num; if (num > 1) return false; } return true; } bool solve () { if (!test()) return false; for (int i = 0; i < cnt; ++i) { init(); int ans = 0; for (int j = 0; j < m; ++j) { if (j == path[i]) continue; int A = Find(no[j].a); int B = Find(no[j].b); if (A != B) { ans += no[j].num; root[A] = B; } } if (!test()) continue; if (ans == sum) return false; } return true; } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i < m; ++i) { scanf("%d%d%d", &no[i].a, &no[i].b, &no[i].num); } sort(no, no + m, cmp); init(); cnt = sum = 0; for (int i = 0; i < m; ++i) { int A = Find(no[i].a); int B = Find(no[i].b); if (A != B) { root[A] = B; path[cnt++] = i; sum += no[i].num; } } if (solve()) printf("%d\n", sum); else printf("Not Unique!\n"); } return 0; }
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
最小生成树(MST)问题
最小生成树的prim算法.可导入多种文件计算
使用两种最小生成树的方法进行聚类,并对效果进行比较,处理了8种典型二维图像和压缩后的三维图像
最小生成树,使用PRIM方法生成最小生成树。
[摘要] 选择一颗生成树,使之总的消费最少,也就是要构造连通网的最小代价生成树(简称为最小生成树)的问题,一颗生成树的代价就是树上各边的代价之和,构造最小生成树可以有多种算法,其中多数算法利用了MST的性质...
数据结构:C++语言实现最小生成树的算法。
一般都是求图的最小生成树,本程序是带权图的最大生成树(搜索树)的算法实现,
网络最小生成树算法,利用numpy实现,MST 矩阵模型
北京大学最小生成树(MST)问题及其扩展
最小生成树问题。多线程编程、并行计算。使用OpenMP计算最小生成树。
从PVST+到MST移植生成树的配置示例
C#,最小生成树(MST)博鲁夫卡(Boruvka)算法的源代码。Boruvka算法用于查找边加权图的最小生成树(MST),它早于Prim和Kruskal的算法,但仍然可以被认为是两者的关联。1926年,奥塔卡·博鲁夫卡(Otakar Boruvka...
mst 用最小生成树聚类
一种新的最小生成树算法,罗竣友,尤众,本文提出一种新的算法以完成加权连通图的最小生成树(minimum spanning tree, MST)。该算法具有以下优点:1,由于主要以排序为主,因此比较�
数学建模常用经典算法集合均已成功编译-最小生成树算法MSTA.rar 数学建模常用经典算法集合(均已成功编译) 有偿代做,如有需要请联系QQ 1170906655,中介勿扰! 层次分析算法AHP.rar ...
自己写的最小生成树算法,请自己在同一个目录下建立一个gtest。txt的文件。 然后编译,这是在linux下写的,应该移植没有问题 C语言写的
Prim算法(普里姆算法),是1930年捷克数学家算法沃伊捷赫·亚尔尼克(Vojtěch Jarník)最早设计; 1957年,由美国计算机科学家罗伯特·普里姆独立实现;...(4)此时由所有边构成的树即为最小生成树。
本文中,我们提出一种新的全分布式算法来在一般的通讯网络中构造一棵最小生成树(MST)。在执行过程中,算法维系着一个跨所有组成员的不相交的树集。每棵树最初只由一个节点构成,每棵树独立的通过连接最近的树进行...
最小生成树 (MST),已被广泛用于广泛的科学领域与日常生活中,例如 粒子物理学(区分对撞机碰撞中的事件类别)、天文学(探测星团中的质量分离)、导航路线计算,近几年也不断有新的最小生成树算法被提出,在新的...