找到气体容器的最小必要体积

Question

我在比赛的某个地方发现了这个问题，但还没能想出解决办法。

There is the N cities with coordinates (x, y). I have to go from first city and reach the second city. There is a gas station in each city. So I have to find minimum necessary volume of gas container to reach the final city. For example:

Input:
3
17 4
19 4
18 5
Output:
1.414

这里，我的方法是：1->3->2

我正在使用简单的暴力破解方法，但是速度太慢了。如何优化我的代码？也许有更好的解决方案？

#include <iostream>
#include <algorithm>
#include <stack>
#include <math.h>
#include <cstring>
#include <iomanip>
#include <map>
#include <queue>
#include <fstream>
using namespace std;

int n, used[203];

double min_dist;

struct pc {
    int x, y;
};

pc a[202];

double find_dist(pc a, pc b) {
    double dist = sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) );
    return dist;
}

void functio(double d, int used[], int k, int step) {
    used[k] = 1;
    if(k == 1) {
        if(d < min_dist) {
            min_dist = d;
        }
        used[k] = 0;
        return;
    }

    for(int i = 1; i < n; ++i) {
        if(i != k && used[i] == 0) {
            double temp = find_dist(a[k], a[i]);

            if(temp > d) {
                if(temp < min_dist)
                functio(temp, used, i, step + 1);
            }
            else {
                if(d < min_dist)
                functio(d, used, i, step + 1);
            }
        }
    }
    used[k] = 0;
}

int main() {

    cin >> n;

    for(int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;

    min_dist = 1000000;
    memset(used, 0, sizeof(used));
    functio(0, used, 0, 0);
    cout << fixed  << setprecision(3) << min_dist << endl;
}

Answer 1

所以您要在算法中优化的是您在两个城市之间旅行的最长距离。因为这就是您的油箱需要多大。这是最短路径的一个变体，因为你正在尝试优化整个路径长度。

我认为你可以摆脱这个：

制作边列表。 (每对城市之间的距离)
从列表中删除最长的边，除非这会导致目的地无法到达。
一旦你不能再删除最长的路径，那就意味着这是你到达目的地的限制因素。剩下的路线已经不重要了。

那么最后你应该有一个组成源和目标之间路径的边列表。

我还没有证明这个解决方案是最优的，所以不能保证。但是考虑一下：如果你去掉最长的路径，只有更短的路径可以走，所以最大腿距离不会增加。

关于复杂度，时间复杂度是O(n log n)，因为你要对边进行排序。
内存复杂度为 O(n^2)

这可能不是最有效的算法，因为它是一种图形算法，并没有利用城市位于欧氏平面上的事实。那里可能有一些优化...

Answer 2

最小生成树具有整洁的属性编码顶点之间的所有路径，使路径上最长边的长度最小化。对于欧几里得 MST，您可以计算 Delaunay 三角剖分，然后运行您最喜欢的 O(m log n) 时间算法（在具有 m = O(n) 边的图上）总共运行ning O(n log n) 的时间。或者，您可以运行 Prim 为具有良好常数的 O(n^2) 时间算法提供一个朴素的优先级队列（特别是如果您利用 SIMD）。

Answer 3

您可以使用二进制搜索将时间复杂度降低到 O(n^2*log(n))，这将运行在 1 秒的时间限制内。二分搜索背后的想法是，如果我们可以使用 x 容量从城市 1 到达城市 2，则无需检查更大容量的容器。如果我们无法使用它，那么我们需要超过 x 的体积。要检查我们是否可以使用 x 体积到达城市 2，您可以使用 BFS。如果两个城市彼此之间的距离在 x 以内，则可以从一个城市移动到另一个城市，我们可以说它们由边连接。

代码：

int vis[203];
double eps=1e-8;

struct pc {
    double x, y;
};

double find_dist(pc &a, pc &b) {
    double dist=sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
    return dist;
}

bool can(vector<pc> &v, double x) {  // can we reach 2nd city with volume x
    int n=v.size();
    vector<vector<int>> graph(n, vector<int>(n, 0));  // graph in adjacency matrix form
    // set edges in graph
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i==j) continue;  //same city
            double d=find_dist(v[i], v[j]);
            if(d<=x) graph[i][j]=1; // can reach from city i to city j using x volume
        }
    }


    // perform BFS
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(0); // we start from city 0 (0 absed index)
    vis[0]=1;
    while(!q.empty()) {
        int top=q.front();
        q.pop();
        if(top==1) return true; // can reach city 2 (1 in 0-based index)
        for(int i=0; i<n; i++) {
            if(top!=i && !vis[i] && graph[top][i]==1) {
                q.push(i);
                vis[i]=1;
            }
        }
    }
    return false; // can't reach city 2
}


double calc(vector<pc> &v) {  // calculates minimum volume using binary search
    double lo=0, hi=1e18;
    while(abs(hi-lo)>eps) {
        double mid=(lo+hi)/2;
        if(can(v, mid)) {
            hi=mid;   // we need at most x volume
        } else{
            lo=mid;  // we need more than x volumer
        }
    }
    return lo;
}

找到气体容器的最小必要体积

Finding minimum necessary volume of gas container

c++

algorithm

brute-force