本文共 3379 字，大约阅读时间需要 11 分钟。

POJ - 1679 The Uinque MST

题意

问给定的图是否有唯一的最小生成树

思路

• 次小生成树

• 利用Prim算法求最小生成树，选择最小的边时进行判断：

  * 是否有两个或者以上的未选择顶点到已选顶点集合的权值相等，若有则不唯一。 * 在松弛操作计算的时候也要判断刚加进去的顶点的权值是否相等。

代码

• 次小生成树

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;/* * 次小生成树 * 求最小生成树时，用数组Max[i][j]来表示MST中i到j最大边权 * 求完后，直接枚举所有不在MST中的边，替换掉最大边权的边，更新答案 * 点的编号从0开始 */const int MAXN = 110;const int INF = 0x3f3f3f3f;bool vis[MAXN];int lowc[MAXN];int pre[MAXN];int Max[MAXN][MAXN]; //Max[i][j]表示在最小生成树中从i到j的路径中的最大边权bool used[MAXN][MAXN];int Prim(int cost[][MAXN], int n){
       int ans = 0;    memset(vis, false, sizeof(vis));    memset(Max, 0, sizeof(Max));    memset(used, false, sizeof(used));    vis[0] = true;    pre[0] = -1;    for (int i = 1; i < n; i++)    {
           lowc[i] = cost[0][i];        pre[i] = 0;    }    lowc[0] = 0;    for (int i = 1; i < n; i++)    {
           int minc = INF;        int p = -1;        for (int j = 0; j < n; j++)            if (!vis[j] && minc > lowc[j])            {
                   minc = lowc[j];                p = j;            }        if (minc == INF)            return -1;        ans += minc;        vis[p] = true;        used[p][pre[p]] = used[pre[p]][p] = true;        for (int j = 0; j < n; j++)        {
               if (vis[j])                Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]);            if (!vis[j] && lowc[j] > cost[p][j])            {
                   lowc[j] = cost[p][j];                pre[j] = p;            }        }    }    return ans;}int ans;int smst(int cost[][MAXN], int n){
       int Min = INF;    for (int i = 0; i < n; i++)        for (int j = i + 1; j < n; j++)            if (cost[i][j] != INF && !used[i][j])            {
                   Min = min(Min, ans + cost[i][j] - Max[i][j]);            }    if (Min == INF)        return -1; //不存在    return Min;}int cost[MAXN][MAXN];int main(){
       int T;    int n, m;    scanf("%d", &T);    while (T--)    {
           scanf("%d%d", &n, &m);        int u, v, w;        for (int i = 0; i < n; i++)            for (int j = 0; j < n; j++)            {
                   if (i == j)                    cost[i][j] = 0;                else                    cost[i][j] = INF;            }        while (m--)        {
               scanf("%d%d%d", &u, &v, &w);            u--;            v--;            cost[u][v] = cost[v][u] = w;        }        ans = Prim(cost, n);        if (ans == -1)        {
               printf("Not Unique!\n");            continue;        }        if (ans == smst(cost, n))            printf("Not Unique!\n");        else            printf("%d\n", ans);    }    return 0;}
      
     
    
   

• Prim

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;#define INF INT_MAX-100 int map[105][105],dis[105];int m,n;bool visit[105]; int Prime()  {
     	int j,k;    int temp,ans=0;    for (int i=1;i<=n;i++)        dis[i]=map[1][i];    visit[1]=true;    for (int i=1;i
       
        map[k][j])					 dis[j]=map[k][j];				 else if (dis[j]==map[k][j] && dis[j]!=INF)					 return -1;    }     return ans;  } void init(){
   	for (int i=1;i<=n;i++)		for (int j=1;j<=n;j++)			map[i][j]=INF;	for (int i=1;i<=n;i++)		map[i][i]=0;	memset(visit,false,sizeof(visit));} int main (){
   	int T;	scanf("%d",&T);	while (T--)	{
   		int x,y,w;		scanf("%d%d",&n,&m);		init ();		for (int i=0;i
       
      
     
    
   

转载地址：https://blog.csdn.net/qq_43826794/article/details/102786280 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！