基于prim算法的TSP问题的近似算法求解c++代码

以下是基于prim算法的TSP问题的近似算法的C++代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 1005;
const double INF = 1e9;
const double eps = 1e-8;

int n;
double x[MAXN], y[MAXN];
double d[MAXN][MAXN];
int vis[MAXN];

double prim() {
    double ans = 0;
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    for (int i = 1; i < n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == 0 || d[1][j] < d[1][u])) u = j;
        ans += d[1][u];
        vis[u] = 1;
        for (int v = 1; v <= n; v++)
            if (!vis[v]) d[1][v] = min(d[1][v], d[u][v]);
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
    printf("%.2lf\n", prim() + eps);
    return 0;
}

其中，`x[i]` 和 `y[i]` 表示第 `i` 个点的坐标，`d[i][j]` 表示第 `i` 个点和第 `j` 个点之间的距离。`prim()` 函数实现了prim算法，返回的是近似的最小生成树的权值和。在主函数中，我们读入点的坐标，计算点与点之间的距离，然后输出 `prim()` 函数返回值加上一个很小的值 `eps`，以保证结果的正确性。