The Unique MST
时间限制: 10 Sec 内存限制: 128 MB
提交: 25 解决: 10
[提交][状态][讨论版]
题目描述
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'.
输入
输出
样例输入
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
样例输出
3
Not Unique!
题意：给一个无向图，判断这个图的最小生成树MST是否是唯一的。如果是唯一的，输出最小生成树的值，如果不是唯一的，输出“Not Unique!”
思路：kruskal的应用。详细思路与prim版相似，而且时间空间复杂度都得到了一些优化。
kruskal算法：把所有的边都排个序，从大到小取出，若取出的这条边的两个端点已经连通（用并查集），则换下一条边，n的顶点用n-1条边就可以相连，循环直到n-1条边。
本题：在找最小生成树（mst）的同时，把选中的边（是第几条）都存下来。再进行多次kruskal算法，每次模拟删除一条边，寻找一条新的边，得到边权和为mst2，判断mst==mst2？即可。
#include <iostream>
#include<string>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
int pre[];
int Rank[];
int mst_e[];
struct node
{
int u, v, w;
};
bool cmp(node x, node y)
{
return x.w < y.w;
}
void init()//初始化
{
int i;
for (i = ; i <= n; i++) pre[i] = i;
memset(Rank, , sizeof(Rank));
}
int find(int x)//找根
{
if (pre[x] == x) return x;
return pre[x] = find(pre[x]);
}
void unite(int x, int y)//压缩合并
{
if (Rank[x] < Rank[y]) pre[x] = y;
else
{
pre[y] = x;
if (Rank[x] == Rank[y]) Rank[x]++;
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
init();
node a[];
int i;
for (i = ; i <= m; i++)
{
cin >> a[i].u >> a[i].v >> a[i].w;
}
sort(a + , a + + m, cmp);
int mst = ;
int k = ;
for (i = ; i <= m; i++)//第一次kruskal算法
{
int x = find(a[i].u);
int y = find(a[i].v);
if (x != y)
{
unite(x, y);
mst = mst + a[i].w;
mst_e[k++] = i;// 记录下MST的边。
}
}
int edge_num = k-;
bool uni = ;//记录是不是唯一
int mst2, num;
for (k =; k <=edge_num; k++)
{//遍历每一条MST里的边，一次次模拟删除
init();//每进行一次kruskal算法，就初始化一次
mst2 = ;
num = ;
for (i = ; i <= m; i++)
{
if (i == mst_e[k]) continue;//模拟删除
int x = find(a[i].u);
int y = find(a[i].v);
if (x != y)
{
unite(x, y);
mst2 = mst2 + a[i].w;
num++;
}
if (num != edge_num) continue;//边数没达到就继续0
if (mst2 == mst)
{
uni = ;
break;
}
}
if (uni == ) break;
}
if (uni) cout << mst << endl;
else cout << "Not Unique!" << endl;
}
return ;
}