Farthest Insertion的c++源码

以下是Farthest Insertion算法的C++代码示例：

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

const int N = 2005;

int n;
double dis[N][N];
bool st[N];
double res;
vector<int> path;

double get_dist(int a, int b)
{
    double dx = fabs(x[a] - x[b]);
    double dy = fabs(y[a] - y[b]);
    return sqrt(dx * dx + dy * dy);
}

void farthest_insertion()
{
    path.push_back(1);
    st[1] = true;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        double maxv = -1e8;
        for (int j = 1; j <= n; j ++ )
            if (!st[j])
            {
                double minv = 1e8;
                for (int k = 0; k < path.size() - 1; k ++ )
                {
                    int a = path[k], b = path[k + 1];
                    if (dis[a][j] + dis[j][b] < minv)
                        minv = dis[a][j] + dis[j][b];
                }
                if (minv > maxv)
                {
                    maxv = minv;
                    t = j;
                }
            }
        st[t] = true;
        vector<int>::iterator k;
        double minv = 1e8;
        for (vector<int>::iterator it = path.begin(); it != path.end() - 1; it ++ )
        {
            int a = *it, b = *(it + 1);
            double d = dis[a][t] + dis[t][b] - dis[a][b];
            if (d < minv)
            {
                minv = d;
                k = it + 1;
            }
        }
        path.insert(k, t);
    }

    for (int i = 0; i < path.size() - 1; i ++ )
        res += dis[path[i]][path[i + 1]];
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            dis[i][j] = dis[j][i] = get_dist(i, j);

    farthest_insertion();

    printf("%.2lf\n", res);

    return 0;
}

其中， `get_dist` 函数是用于计算两个城市之间的欧几里得距离。

这段代码的时间复杂度为 $O(n^2 \log n)$，其中 $n$ 为城市数量。