MST算法（POJ 1789

MST算法（POJ 1789）是一种用于求解最小生成树问题的算法。首先，我们需要使用prim算法来求出最小生成树。然后，通过添加边来判断新生成的最小生成树是否具有最小的权值。在POJ上的The Unique MST（1679）题中，要求判断最小生成树是否唯一。但是在其他情况下，我们并不需要进行这样的判断。

相关问题

求解最小支撑树MST的算法原理

最小支撑树 (Minimum Spanning Tree，MST) 是一棵树，它连接了一个无向图中的所有节点，并且总权值最小。求解最小支撑树的算法有多种，下面介绍两种常见的算法：

1. Kruskal算法

Kruskal算法是一种贪心算法，它通过不断选择边来构建最小支撑树。具体步骤如下：

1）将所有边按照权值从小到大排序。

2）从权值最小的边开始，如果这条边的两个端点不在同一个连通块中，则选择这条边，并将这两个端点所在的连通块合并。

3）重复第2步，直到所有节点都在同一个连通块中为止。

2. Prim算法

Prim算法也是一种贪心算法，它通过不断选择节点来构建最小支撑树。具体步骤如下：

1）选择任意一个节点作为起点，将该节点加入最小支撑树中。

2）将与最小支撑树的节点相邻的所有边按照权值从小到大排序。

3）选择权值最小的边所连接的节点，如果该节点不在最小支撑树中，则将该节点加入最小支撑树中。

4）重复第2步和第3步，直到所有节点都在最小支撑树中为止。

以上两种算法都可以求解最小支撑树，它们的时间复杂度都是O(ElogE)，其中E是图中的边数，因此在实际应用中可以根据具体情况选择使用哪种算法。

MST算法求满足三角不等式的TSP问题的C++代码

以下是使用Prim算法求解满足三角不等式的TSP问题的C++代码：

#include<bits/stdc++.h>
using namespace std;

const int INF=1e9;
const int maxn=1005;

int n,cnt;
int dis[maxn][maxn],lowc[maxn];
bool vis[maxn];

void prim()
{
    memset(vis,false,sizeof(vis));
    vis[1]=true;
    for(int i=2;i<=n;i++)
        lowc[i]=dis[1][i];
    for(int i=2;i<=n;i++)
    {
        int p,minn=INF;
        for(int j=2;j<=n;j++)
            if(!vis[j]&&minn>lowc[j])
            {
                minn=lowc[j];
                p=j;
            }
        cnt+=minn;
        vis[p]=true;
        for(int j=2;j<=n;j++)
            if(!vis[j]&&lowc[j]>dis[p][j])
                lowc[j]=dis[p][j];
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>dis[i][j];
    prim();
    cout<<cnt<<endl;
    return 0;
}

其中，dis[i][j]表示点i到点j的距离，cnt表示最小生成树的权值和。