http://poj.org/problem?id=1679
题意:问最小生成树是否唯一
思路:
用Kruskal先求最小生成树,结果即为min,把所用到的边记录下来(这里是记录的对应的下表),然后枚举这些边,
每次去掉一个边再求一次最小生成树,结果为tmin,如果能构成最小生成树tmin==min,则说明最小生成树不唯一
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!
代码自己YY吧……
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 0x3fffffff
int n, k, pre[105], num[10005], ind;
struct road{
int a, b;
int weight;
}r[10005];
bool cmp (road x, road y)
{
return x.weight < y.weight;
}
int find (int a)
{
while (a != pre[a])
a = pre[a];
return a;
}
int MST (int key)
{
int mincost = 0, i, tp = 0, A, B;
for (i = 1; i <= n; i++)
pre[i] = i;
for (i = 0; i < k; i++)
{
if (i == key)
continue;
A = find (r[i].a);
B = find (r[i].b);
if (A != B)
{
if (key == -1)
num[ind++] = i;
mincost += r[i].weight;
pre[B] = A;
}
}
for (i = 1; i <= n; i++)
{
if (pre[i] == i)
{
tp++;
if (tp > 1)
return inf;
}
}
return mincost;
}
int main()
{
int m, t, i, a, b, w, mins, tmins, tp;
scanf ("%d", &t);
while (t--)
{
k = ind = 0;
scanf ("%d%d", &n, &m);
while (m--)
{
scanf ("%d%d%d", &a, &b, &w);
r[k].a = a;
r[k].b = b;
r[k].weight = w;
k++;
}
sort (r, r+k, cmp);
mins = MST (-1);
tmins = inf;
for (i = 0; i < ind; i++)
{
tp = MST (num[i]);
if (tmins > tp)
tmins = tp;
}
if (tmins > mins)
printf ("%d\n", mins);
else puts ("Not Unique!");
}
return 0;
}
分享到:
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
### 最小生成树(MST)问题详解 #### 一、最小生成树概念 最小生成树(Minimum Spanning Tree, MST)问题是计算机科学与图论领域中的一个重要问题,尤其是在网络设计、电路板布线等领域有着广泛的应用。对于一个连通的...
标题“poj1251 最小生成树”是一个编程竞赛题目,来源于著名的在线编程平台POJ(Programming Online Judge)。这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,...
【标题】"POJ 1679 练习克鲁斯卡尔Kruskal算法" 在图论领域,克鲁斯卡尔(Kruskal)算法是一种用于解决最小生成树问题的有效方法。这个问题涉及到在一个加权无向图中找到一棵包括所有顶点的树,其边的权重之和尽...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
题目来自POJ平台,编号为1639,题目名称为“Picnic Planning”,主要考查的是算法中的最小度限制生成树问题。 ### 问题定义 给定一个无向图,其中包含一个特殊节点s(称为公园),要求构建一个生成树,使得该生成树...
标题中的“POJ 1789 最小生成树之prim算法”指的是一个在线编程竞赛题目,来源于普林斯顿开放在线课程(POJ)平台。该题目要求参赛者实现Prim算法,这是一种解决图论问题中寻找最小生成树的经典算法。最小生成树是在...
这些题目均涉及到图论中的一个核心概念——最小生成树(Minimum Spanning Tree, MST),它在计算机科学,尤其是网络设计和优化问题中有着广泛应用。最小生成树问题是寻找一个无权图或有权图中的边的子集,这个子集...
3. **P1679(Unique_MST_prim).cpp 和 P1679(Unique_MST_kruskal).cpp** - 这两个文件都涉及了“唯一最小生成树”问题。Prim和Kruskal是两种常见的求解最小生成树的算法。在某些情况下,图可能有唯一的最小生成树...
5. **度限制最小生成树构建**:最终的`DL_MST()`函数将上述步骤综合起来,完成度限制最小生成树的构建。它首先通过DFS确定连通分量,然后在每个连通分量内调用Prim算法得到局部最小生成树,最后通过扩展Prim算法确保...
从提供的压缩包子文件名称"PKU_1861_最小生成树"来看,我们可以推测这道题目与图论中的"最小生成树"(Minimum Spanning Tree, MST)问题有关。最小生成树是图论中的一个重要概念,它要求找到一个无向加权图的边子集...
【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...
poj 1611 The Suspects 代码 并查集的应用
### POJ1679 TheUniqueMST **题目链接:** <http://acm.pku.edu.cn/JudgeOnline/problem?id=1679> **核心知识点:** - **问题描述:** 验证给定图的最小生成树是否唯一。 - **解题思路:** 可以先通过Prim或...
【标题】"POJ1027 - The Same Game"是一个经典的编程竞赛题目,源自北京大学的在线编程平台POJ(Problem Online Judge)。该题目主要考察的是动态规划和矩阵链乘法的知识,要求参赛者编写程序解决一个具有策略性的...
标题中的“POJ 1054 The Troublesome Frog”是一个编程竞赛题目,来源于“Programming Online Judge”(POJ)平台。这个平台是程序员们练习算法和编程技能的地方,通常涉及各种数据结构和算法的问题。题目...
在【压缩包子文件的文件名称列表】中,"poj 2485 Highways (最小生成树)"可能是题目提供的样例输入和输出文件,用于检验自己编写的程序是否正确。这些样例通常包含了各种边界情况和特殊案例,以确保算法的鲁棒性。 ...
北大POJ1163-The Triangle
* 递归和分治法:递归和分治法是指将问题分解成多个小问题,通过解决小问题来解决大问题,如 poj3295。 * 递推:递推是指通过前一个结果来计算当前结果的方法,如 poj1068、poj2632、poj1573、poj2993、poj2996。 * ...
2. **POJ1679 TheUniqueMST** - **题意**:判断最小生成树是否唯一。 - **解法**:Prim算法即可解决,虽然实现起来容易出错。 3. **POJ2728 DesertKing** - **题意**:要求找到具有最优比率的生成树。 - **...