首页 > 代码库 > POJ1679 The Unique MST【Kruskal】【次小生成树】
POJ1679 The Unique MST【Kruskal】【次小生成树】
The Unique MST
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 21304Accepted: 7537
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 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string ‘Not Unique!‘.Sample Input
23 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!
题目大意：给你N个点M条边的图，问：图的最小生成树是否唯一。
思路：参考算法书，在kruskal算法的基础上进行修改，加入(x,y)两点在最小生成树
上路径最长的边的计算。使用了链式前向星记录每个集合中含有那些点。
在合并集合(邻接表)的时候，为了方便，加入了End[]记录邻接表尾节点的位置。
MST表示最小生成树的大小，SecMST表示次小生成树的大小。最后判断是否想等
即可。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1010;
const int MAXM = 100010;
int father[MAXN];
int find(int x)
{
if(x != father[x])
father[x] = find(father[x]);
return father[x];
}
struct Node
{
int from;
int to;
int w;
bool vis;
};
Node Edges[MAXM];//存储边信息
bool cmp(Node a, Node b)
{
return a.w < b.w;
}
//链式前向星
struct Node1
{
int to;
int next;
};
Node1 Vertex[MAXN];//边数组，表示结点连向的边
int N,M;
int head[MAXN]; //邻接表头结点位置
int End[MAXN]; //邻接表尾结点位置，方便合并
int Len[MAXN][MAXN];//图中两点之间在最小生成树上路径最长的边
void Kruskal()
{
int x,y,k = 0;
int ans = 0;
//初始化邻接表，每个节点初始的时候添加一条指向自己的边，表示结点i各自为一个集合
memset(head,-1,sizeof(head));
memset(End,-1,sizeof(End));
for(int i = 1; i <= N; i++)
{
Vertex[i].to = i;
Vertex[i].next = head[i];
End[i] = i;
head[i] = i;
}
sort(Edges,Edges+M,cmp);//边按权值排序
for(int i = 0; i < M; i++)
{
if(k == N-1)
break;
if(Edges[i].w < 0)
continue;
x = find(Edges[i].from);
y = find(Edges[i].to);
if(x != y)
{
//遍历两个节点所在的集合
for(int w = head[x]; w != -1; w = Vertex[w].next)
{
for(int v = head[y]; v != -1; v = Vertex[v].next)
{
Len[Vertex[w].to][Vertex[v].to] = Len[Vertex[v].to][Vertex[w].to] = Edges[i].w;
//当前加入的边一定是加(x,y)边成环后删去的除(x,y)外长度最大的边
}
}
Vertex[End[y]].next = head[x];//合并两个邻接表，表示两点已连边连在一个集合中，最终连成一个最小生成树
head[x] = head[y];
End[y] = End[x];
father[y] = x;
k++;
Edges[i].vis = true;
}
}
}
int main()
{
int T,x,y,w;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&M);
for(int i = 1; i <= N; i++)
father[i] = i;
memset(Len,0x7f,sizeof(Len));
for(int i = 0; i < M; i++)
{
scanf("%d%d%d",&x,&y,&w);
Edges[i].from = x;
Edges[i].to = y;
Edges[i].w = w;
Edges[i].vis = false;
}
int MST,SecMST;
Kruskal();
MST = 0;//最小生成树长度
for(int i = 0; i < M; i++)
{
if(Edges[i].vis)
MST += Edges[i].w;
}
SecMST = 0xfffff0;
for(int i = 0; i < M; i++)
{
if(!Edges[i].vis)//加边，并删去最小生成树上的边
SecMST = min(SecMST,MST+Edges[i].w - Len[Edges[i].from][Edges[i].to]);
}
if(SecMST == MST)
printf("Not Unique!\n");
else
printf("%d\n",MST);
}
return 0;
}
POJ1679 The Unique MST【Kruskal】【次小生成树】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。