本文主要是介绍POJ 1679 The Unique MST （次小生成树Prime/Kruskal），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：判断图中的最小生成树是否唯一。
题解：只需验是否存在两个或两个以上权值相同的最小生成树。注意：1.图中任意两点间最多只有一条无向边； 2.图可能不连通（此时mst = 0)。
Prime ：复杂度 O( V ^ 2 )
#include <iostream>
using namespace std;
#define MAX 101
#define INF 999999999
#define max(a,b) (a>b?a:b)
int dis[MAX], pre[MAX];
int edge[MAX][MAX];
int maxVal[MAX][MAX];
bool inTree[MAX][MAX];
bool vis[MAX];
int Prime ( int n )
{
int i, j, k, minc, mst;
for ( i = 1; i <= n; i++ )
{
dis[i] = edge[1][i];
vis[i] = false;
pre[i] = 1;
}
dis[1] = mst = 0;
vis[1] = true;
for ( i = 2; i <= n; i++ )
{
minc = INF; k = -1;
for ( j = 1; j <= n; j++ )
{
if ( ! vis[j] && dis[j] < minc )
{
minc = dis[j];
k = j;
}
}
if ( minc == INF ) return -1; // 图不连通，没有找到最小生成树
mst += minc;
vis[k] = true;
inTree[pre[k]][k] = inTree[k][pre[k]] = true; // 记录加入的树中的边
for ( j = 1; j <= n; j++ )
if ( vis[j] == true )
maxVal[j][k] = max ( maxVal[j][pre[k]], edge[pre[k]][k] ); // 找j-k的路径上权值最大的那条边，并记录在maxVal[j][k]中
for ( j = 1; j <= n; j++ )
{
if ( ! vis[j] && dis[j] > edge[k][j] )
{
dis[j] = edge[k][j];
pre[j] = k; // 修正前驱
}
}
}
return mst;
}
void initial ( int n )
{
for ( int i = 1; i < n; i++ )
{
for ( int j = i + 1; j <= n; j++ )
{
edge[i][j] = edge[j][i] = INF;
inTree[i][j] = inTree[j][i] = 0;
maxVal[i][j] = maxVal[j][i] = 0;
}
}
}
int main()
{
int t, n, m, u, v, w;
scanf("%d",&t);
while ( t-- )
{
scanf("%d%d",&n,&m);
initial ( n );
while ( m-- )
{
scanf("%d%d%d",&u,&v,&w);
edge[u][v] = edge[v][u] = w;
}
int mst = Prime ( n );
if ( mst < 0 ) { printf("0\n"); continue; }
int res;
bool flag = false;
for ( int i = 1; i < n; i++ )
{
for ( int j = i + 1; j <= n; j++ )
{
if ( inTree[i][j] || edge[i][j] == INF ) continue; // 边edge[i][j]在树中或者i,j之间无边
res = mst + edge[i][j] - maxVal[i][j]; // 用边edge[i][j]， 替换i-j路径上权值最大的那条边，得到一棵新的生成树
if ( res == mst ) { flag = true; break; }
}
if ( flag ) break;
}
if ( flag )
printf("Not Unique!\n");
else
printf("%d\n",mst);
}
return 0;
}
Kruskal ：复杂度 O(E*logE + V*E)
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX 10000
struct Edge
{
int u, v, w;
} edge[MAX];
int father[MAX];
int rank[MAX]; // 记录每个集合的元素个数
int mst[MAX]; // 记录最小生成树的边
int cmp ( const void *a, const void *b )
{
Edge *c = (Edge*)a;
Edge *d = (Edge*)b;
return c->w - d->w;
}
int find_set ( int x )
{
if ( father[x] != x )
father[x] = find_set ( father[x] );
return father[x];
}
int Kruskal ( int n, int m )
{
int fu, fv, i, sum = 0;
for ( i = 1; i <= n; i++ )
{
father[i] = i;
rank[i] = 1;
}
for ( i = 1; i <= m; i++ )
{
fu = find_set(edge[i].u);
fv = find_set(edge[i].v);
if ( fu == fv ) continue;
sum += edge[i].w;
mst[++mst[0]] = i;
father[fu] = fv;
rank[fv] += rank[fu];
if ( rank[fv] == n || rank[fu] == n )
return sum;
}
return 0;
}
int solve ( int n, int m )
{
qsort ( edge+1, m, sizeof(Edge), cmp );
memset(mst,0,sizeof(mst));
int res = Kruskal ( n, m );
if ( res == 0 ) return 0;
int fu, fv, k, i, sum;
for ( k = 1; k <= mst[0]; k++ ) // 枚举最小生成树中的每一条边，将其删去，并求最小生成树
{
sum = 0;
for ( i = 1; i <= n; i++ )
{
father[i] = i;
rank[i] = 1;
}
for ( i = 1; i <= m; i++ )
{
if ( i == mst[k] ) continue;
fu = find_set(edge[i].u);
fv = find_set(edge[i].v);
if ( fu == fv ) continue;
sum += edge[i].w;
father[fu] = fv;
rank[fv] += rank[fu];
if ( rank[fv] == n || rank[fu] == n ) break;
}
if ( sum == res ) return -1;
}
return res;
}
int main()
{
int t, n, m;
scanf("%d",&t);
while ( t-- )
{
scanf("%d%d",&n,&m);
for ( int i = 1; i <= m; i++ )
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
int ans = solve ( n, m );
if ( ans == -1 )
printf("Not Unique!\n");
else
printf("%d\n",ans);
}
return 0;
}
这篇关于POJ 1679 The Unique MST （次小生成树Prime/Kruskal）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
