The Unique MST 次小生成树

传送门

分析

这道题的题意是求一张图中的最小生成树和次小生成树，然后判断是否相等

首先我们来了解一下什么是次小生成树，次小生成树的意思就是和最小生成树最少要有一条边不一样的生成树，所以，我们可以先构建最小生成树，将用到的边进行标记，最后得倒一棵生成树，在树中dfs以求出任意两点之间的最长距离，然后引入未进行标记的边已替换最小生成树中的边，假设最小生成树为sum，则替换完之后为
sum - d[a][b] + w

将每一条没有标记的边加入，找最小值即可

最后只要最小值和之前求的最小生成树相同即可

其实换而言之就是找一条未标记边代替代替最小生成树中的边，所以只要有一条边的距离和最小生成树中两点距离相同即可

PS：这道题数据有点水，我kruskal忘了给边sort居然也过了。。。

代码

#include <cstring>
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 110,M = N * N;
int h[N],ne[M],e[M],w[M],idx;
int q[N];
int d[N][N];
int n,m;
struct Edge{
int a,b,w;
bool f;
bool operator< (const Edge &t) const{
return w < t.w;
}
}E[M];
void add(int a,int b,int c){
w[idx] = c,ne[idx] = h[a],e[idx] = b,h[a]
=idx++;
}
int find(int x){
if(x != q[x]) q[x] = find(q[x]);
return q[x];
}
void dfs(int u,int fa,int maxd,int x){
d[u][x] = maxd;
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(j == fa) continue;
int t = maxd;
t = max(t,w[i]);
dfs(j,u,t,x);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) q[i] = i;
memset(h,-1,sizeof h);
for(int i = 0;i < m;i++){
scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);
E[i].f = false;
}
int sum = 0;
sort(E,E + m);
for(int i = 0;i < m;i++){
int a = E[i].a,b = E[i].b,w = E[i].w;
int pa = find(a),pb = find(b);
if(pa != pb){
E[i].f = true;
sum += w;
q[pa] = pb;
add(a,b,w);
add(b,a,w);
}
}
for(int i = 1;i <= n;i++) dfs(i,-1,0,i);
int res = 0x3f3f3f3f;
bool flag
= false;
for(int i = 0;i < m;i++){
if(E[i].f) continue;
int a = E[i].a,b = E[i].b,w = E[i].w;
if(d[a][b] == w){
flag = true;
break;
}
}
if(flag) puts("Not Unique!");
else printf("%dn",sum);
}
return 0;
}

最后

以上就是称心皮带为你收集整理的The Unique MST 次小生成树的全部内容，希望文章能够帮你解决The Unique MST 次小生成树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。