【判断MST的唯一性】POJ 1679 The Unique MST

42 阅读 0 评论 28 点赞

我是靠谱客的博主丰富大地，最近开发中收集的这篇文章主要介绍【判断MST的唯一性】POJ 1679 The Unique MST，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

POJ 1679 The Unique MST

这道题非常非常非常非常非常的坑

不管怎么样吧，过了n久终于过了，而且还很迷。

这个思路还是挺顺利，一发就过了
说说AC思路：

我们将每条边的序号记录在id里
第一次，我们将边权升序，id降序，找到MST，记录MST所用的边的序号
第二次，我们将边权升序，id升序，找到MST，记录MST所用的边的序号
如果两次mst的结果不同，说明没有MST唯一
如果相同，那么我们将两次找到的MST所用的边作比较，如果完全相同，说明MST唯一，否则，MST不唯一

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <list>
#include <map>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxN = 200 + 5;
const int maxM = 4e5;
int n, m;
struct node{
int u, v, w, id;
node(int a = 0, int b = 0, int c = 0, int d = 0) : u(a), v(b), w(c), id(d) {}
}info[maxM];
bool cmp_one(node n1, node n2)
{
if(n1.w == n2.w)
return n1.id < n2.id;
return n1.w < n2.w;
}
bool cmp_two(node n1, node n2)
{
if(n1.w == n2.w)
return n1.id > n2.id;
return n1.w < n2.w;
}
int root[maxN], child[maxN], high[maxN];
void init(int x)
{
for(int i = 0; i <= x; i ++ )
{
root[i] = i;
child[i] = 1;
high[i] = 0;
}
}
int Find(int x) { return root[x] == x ? x : root[x] == Find(root[x]); }
int Same(int x, int y) { return Find(x) == Find(y); }
void Merge(int x, int y)
{
x = Find(x); y = Find(y);
if(child[x] < child[y] || high[x] < high[y])
{
root[x] = y;
child[x] += child[y];
}
else
{
root[y] = x;
child[y] += child[x];
if(high[x] == high[y]) high[x] ++ ;
}
}
int used_one[maxN], used_two[maxN];
int Kruskal(int x)
{
init(n);
int edge_num = 0, ans = 0;
for(int i = 0; i < m; i ++ )
{
if(!Same(info[i].u, info[i].v))
{
Merge(info[i].u, info[i].v);
ans += info[i].w;
if(x == 1)
used_one[edge_num ++] = info[i].id;
else
used_two[edge_num ++] = info[i].id;
}
}
return ans;
}
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", &info[i].u, &info[i].v, &info[i].w);
info[i].id = i;
}
sort(info, info + m, cmp_one);
int ans_one = Kruskal(1);
sort(info, info + m, cmp_two);
int ans_two = Kruskal(2);
if(ans_one != ans_two)
printf("%dn", ans_one);
else
{
int flag = 0;
sort(used_one, used_one + n - 1);
sort(used_two, used_two + n - 1);
for(int i = 0; i < n - 1; i ++ )
{
if(used_one[i] == used_two[i])//完全相同，那就是没有重复的
continue;
else
flag = 1;//有其他的MST存在
}
if(!flag)
printf("%dn", ans_one);
else
printf("Not Unique!n");
}
}
return 0;
}

再来说说另外一种思路，这种思路就是我WA了n发的那个

首先我们跑一下MST，记录下mst，与此同时我们记录下用到的边
然后我们枚举每一条用到的边，去掉该边，看是不是还有一颗相同权值和的MST存在

我WA在了我在Kruskal的for循环里判断了一下edge_num == n - 1?如果是就直接break，然后就WA了。如果放在外面，直接mst = ans，就AC了，……迷

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int maxN = 1000 + 7;
const int maxM = 2e6;
int n, m; int mst;
struct node{
int u, v, w;
friend bool operator < (node n1, node n2) { return n1.w < n2.w; }
}ve[maxM];
int root[maxN], high[maxN], child[maxN];
int Find(int x) { return root[x] == x ? x : root[x] = Find(root[x]); }
int Same(int x, int y) { return Find(x) == Find(y); }
void Merge(int x, int y)
{
x = Find(x) ; y = Find(y);
if(high[x] < high[y] || child[x] < child[y])
{
root[x] = y;
child[y] += child[x];
}
else
{
root[y] = x;
child[x] += child[y];
if(high[x] == high[y]) high[x] ++;
}
}
void init()
{
for(int i = 0; i <= n ; i ++ )
{
root[i] = i;
high[i] = 0;
child[i] = 1;
}
}
bool Kruskal()
{
int used[maxN];
sort(ve , ve + m);
init();
int edge_num = 0;
int ans = 0;
for(int i = 0; i < m ; i ++ )
{
if(!Same(ve[i].u, ve[i].v))
{
Merge(ve[i].u, ve[i].v);
ans += ve[i].w;
used[edge_num ++ ] = i;
}
}
mst = ans;
for(int pos = 0; pos < n - 1; pos ++ )
{
init(); edge_num = 0; ans = 0;
for(int i = 0; i < m ; i ++ )
{
if(i != used[pos] && !Same(ve[i].u, ve[i].v))
{
Merge(ve[i].u, ve[i].v);
edge_num ++ ;
ans += ve[i].w;
}
if(edge_num == n - 1 && ans == mst)
return true;
}
}
return false;
}
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", &ve[i].u, &ve[i].v, &ve[i].w);
if(Kruskal())
printf("Not Unique!n");
else
printf("%dn", mst);
}
return 0;
}