POJ 1679 The Unique MST （最小生成树）

时间：2024-01-21 22:52:15

The Unique MST

题目链接：

http://acm.hust.edu.cn/vjudge/contest/124434#problem/J

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'.

Input


The first line contains a single integer t (1

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!


##题意：

求最小生成树并判断是否唯一.


##题解：

做法一：
先求一次最小生成树并记录MST中的边，枚举删除MST中的边，判断删除后的结果是否与删除前相同.
这样做一定要注意：删边后可能最小生成树不存在(求得的结果不联通).
很遗憾做了久都没过. 挖坑待填.

做法二：
考虑MST中每条边的作用：
kruskal在枚举边时，当一条边连接了并查集中不同的两个集合时，便把它加到结果中.
那么MST中边的作用是连接不同的两个集合.
如果存在多个MST，那么一定有一条或多条边可以起到相同的作用，即：
长度相等 且 连接集合的作用也相同.
基于以上理论，在kruskal过程中对长度相同的边作特判即可.

做法三：
直接求次小生成树.


##代码：
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 110
#define mod 100000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;

struct node{

int left,right,cost;

}road[maxn*maxn];

vector ans_edge;

bool vis_edge[maxn];

int cmp(node x,node y) {return x.cost<y.cost;}

int p[maxn],m,n;

int find(int x) {return p[x]=(p[x]==x? x:find(p[x]));}

int kruskal()

{

int ans = 0;

for(int i=1;i<=n;i++) p[i]=i;

for(int i=1;i<=m;i++)

{

int x=find(road[i].left);

int y=find(road[i].right);

    if(x == y)continue;

    for(int j=i+1; j<=m; j++) {

        if(road[j].cost != road[i].cost) break;

        if(find(road[j].left) == x && find(road[j].right) == y)

            return -1;

    }

    ans+=road[i].cost;

    p[x]=y;

}

return ans;

}

int main(int argc, char const *argv[])

{

//IN;

int t; scanf("%d", &t);

while(t--)

{

    scanf("%d %d", &n,&m);

    memset(road,0,sizeof(road));

    for(int i=1; i<=m; i++) {

        scanf("%d %d %d", &road[i].left,&road[i].right,&road[i].cost);

        /*一定要维护两端点的相对关系，才方便判断是否有边起到了相同的作用*/

        if(road[i].left > road[i].right) swap(road[i].left, road[i].right);

    }

    sort(road+1,road+m+1,cmp);

    int ans = kruskal();

    if(ans == -1) printf("Not Unique!\n");

    else printf("%d\n", ans);

}

return 0;

}

相关文章