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)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj 1611 The Suspects 代码 并查集的应用
NULL 博文链接:https://128kj.iteye.com/blog/1707218
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
NULL 博文链接:https://128kj.iteye.com/blog/1704752
poj 1611 The Suspects.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 3191 The Moronic Cowmpouter.md
poj 1989 The Cow Lineup.md
poj 3260 The Fewest Coins.md
poj 3901 The Computer Game.md
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
度限制最小生成树代码 摘自POJ1639代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...