找到最低需求量的气体容器

Question

我发现这个问题在某个比赛的某个地方，还没有能够拿出一个解决方案呢。

有N个城市坐标（x，y）的。我必须从第一个 城市去到第二个城市。每个城市都有一个加油站。 所以我必须找到最低容量的气柜达到 最后的城市。 例如：

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

最小生成树具有编码的顶点，最大限度地减少路径上的最长边的长度之间的所有路径的整齐的财产。对于Euclidean MST，可以计算Delaunay三角剖分，然后运行您最喜欢的O（m log n）时间算法（在m = O（n）边的图上），总运行时间为O（n log n）。或者，你可以用一个优秀的常量（尤其是如果你利用SIMD）运行一个O（n^2）时间算法的天真优先级队列来运行Prim。

Answer 2

所以你想在你的算法来优化是什么你们两个城市之间行驶的最长距离。因为这就是你的油箱需要多大。 这是最短路径上的一种变体，因为您试图优化enire路径长度。

我想你可以不用它：

• 使图像边缘的列表。

• （每对城市之间的距离）从列表中删除的最长边，除非这使得目的地不可达。

• 一旦你不能删除的最长路径了，这意味着这是要去的目的地的限制因素。剩下的路线再也没有关系了。

然后最后你应该有一个边缘列表，组成源和目的地之间的路径。

我还没有证明这个解决方案是最优的，所以没有保证。但考虑一下：如果删除最长的路径，则只有较短的路径，所以最大路程不会增加。

---

关于复杂性，时间复杂度为O(n log n)，因为你必须边进行排序。
内存复杂度为O（n^2）

这可能不是最有效的算法，因为它是一个图形算法，并没有使用城市在欧几里得平面上的事实。有可能是一些优化那里...

Answer 3

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

代码：

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; 
}