The Unique MST--次小生成树

题目链接：https://vjudge.net/problem/OpenJ_Bailian-1679

题目大意：n个点，m条边，求最小生成树是不是唯一的。

分析：求最小生成树是否唯一，可以把次小生成树的权值（d2）求出来，与最小生成树的权值（d1）比较，如果d2大于d1，说明唯一，否则不唯一。maxd[i][j]数组存的是点i到点j的路径中，最长的一条边。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int N = 110;
int n, m;
int pre[N], maxd[N][N];
vector<int> G[N];
struct Edge{
int u, v, w;;
bool vis;
}mp[20010];
bool cmp(const Edge a, const Edge b)
{
return a.w < b.w;
}
int find(int x)
{
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
int kruskal()
{
for(int i = 0; i <= n; i++)
{
G[i].clear();
G[i].push_back(i);
pre[i] = i;
}
sort(mp, mp + m, cmp);
int sum = 0, cnt = 0;
for(int i = 0; i < m; i++)
{
if(cnt == n - 1) break;
int x1 = find(mp[i].u);
int x2 = find(mp[i].v);
if(x1 != x2)
{
cnt++;
mp[i].vis = 1;
sum += mp[i].w;
int len1 = G[x1].size();
int len2 = G[x2].size();
for(int j = 0; j < len1; j++)
{
for(int k = 0; k < len2; k++)
maxd[G[x1][j]][G[x2][k]] = maxd[G[x2][k]][G[x1][j]] = mp[i].w;
}
pre[x1] = x2;
for(int j = 0; j < len1; j++)
G[x2].push_back(G[x1][j]);
}
}
int ans = inf;
for(int i = 0; i < m; i++)
{
if(!mp[i].vis)
ans = min(ans, sum + mp[i].w - maxd[mp[i].u][mp[i].v]);
}
if(ans > sum) return sum;
return -1;
}
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", &mp[i].u, &mp[i].v, &mp[i].w);
mp[i].vis = 0;
}
int ans = kruskal();
if(ans != -1) printf("%dn", ans);
else printf("Not Unique!n");
}
return 0;
}

最后

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

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