沙漠之王

之王"/>

沙漠之王

大卫大帝刚刚建立了一个沙漠帝国，为了赢得他的人民的尊重，他决定在全国各地建立渠道，为每个村庄提供水源。

与首都相连的村庄将得到水资源的浇灌。

他希望构建的渠道可以实现单位长度的平均成本降至最低。

换句话说，渠道的总成本和总长度的比值能够达到最小。

他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。

他的工程师对所有村庄的地理位置和高度都做了调查，发现所有渠道必须直接在两个村庄之间水平建造。

由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。

建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。

需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。

输入格式
输入包含多组测试数据。

每组测试数据第一行包含整数N，表示村庄（包括首都）的总数目。

接下来N行，每行包含三个整数x，y，z，描述一个村庄的地理位置，(x,y)为该村庄的位置坐标，z为该村庄的地理高度。

第一个被描述的村庄即为首都。

当输入一行为0时，表示输入终止。

输出格式
每组数据输出一个结果，每个结果占一行。

结果为一个保留三位小数的实数，表示渠道的总成本和总长度的比值的最小值。

数据范围
2≤N≤1000,
0≤x,y<10000,
0≤z≤10000000

输入样例：
4
0 0 0
0 1 1
1 1 2
1 0 3
0
输出样例：
1.000

第一版本TLE了，10组数据过6组。

#include <bits/stdc++.h>using namespace std;struct node {int x, y, z;
} vallege[1001];
double dis[1001][1001];
double heigh[1001][1001];
int N;double distance(node a, node b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}typedef struct Node {double length, cost, weigh;int num;bool operator<(const Node &a) const {return weigh > a.weigh;}
} data;double prim(double mid) {set<int> remain;for (int i = 1; i <= N; i++)remain.insert(i);priority_queue<data> q;data temp;temp.cost = 0;temp.length = 0;temp.num = 1;temp.weigh = 0;q.push(temp);double length = 0, cost = 0;while (!remain.empty()) {int x = q.top().num;if (remain.count(x)) {length += q.top().length;cost += q.top().cost;remain.erase(x);q.pop();for (int it : remain) {temp.cost = heigh[x][it];temp.length = dis[x][it];temp.num = it;temp.weigh = temp.cost - temp.length * mid;q.push(temp);}} else q.pop();}return cost - mid * length;
}int main() {while (true) {cin >> N;if (N == 0)break;for (int i = 1; i <= N; i++) {cin >> vallege[i].x >> vallege[i].y >> vallege[i].z;}for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++) {dis[i][j] = distance(vallege[i], vallege[j]);heigh[i][j] = fabs(vallege[i].z - vallege[j].z);}double left = 0, right = 100, mid;while (fabs(left - right) > 1e-4) {mid = (left + right) / 2;double new_mid = prim(mid);if (new_mid > 0)left = mid;elseright = mid;}printf("%.3f\n", left);}return 0;
}

开始时想不通为什么会超时。别人不用堆优化能过，我用堆优化却超时，为什么越优化越慢呢？
分析算法复杂度发现，prim算法的复杂度为o(n^ 2)，而用二叉堆可以优化到o(mlog(n))，然而对于完全图，m=n*(n-1)/2，因此优化后的时间复杂度为o(n^ 2log(n))，显然比优化前复杂度大。这就出现了越优化越慢的情况。
不用堆优化改为遍历更新最值果然通过了。
AC代码

#pragma GCC optimize(2)#include<bits/stdc++.h>using namespace std;
const int N = 1e3 + 5;
int n;
double pic[N][N], l[N][N], c[N][N], d[N];
bool v[N];
struct {double x, y, z;
} loc[N];void read() {for (int i = 1; i <= n; i++)scanf("%lf%lf%lf", &loc[i].x, &loc[i].y, &loc[i].z);
}void build() {for (int i = 1; i < n; i++)for (int j = i + 1; j <= n; j++) {l[i][j] = l[j][i] = sqrt((loc[i].x - loc[j].x) * (loc[i].x - loc[j].x) + (loc[i].y - loc[j].y) * (loc[i].y - loc[j].y));c[i][j] = c[j][i] = fabs(loc[i].z - loc[j].z);}
}bool prim(double mid) {for (int i = 1; i < n; i++)for (int j = i + 1; j <= n; j++)pic[i][j] = pic[j][i] = mid * l[i][j] - c[i][j];memset(d, -0x3f, sizeof(d));memset(v, false, sizeof(v));d[1] = 0;for (int i = 1; i < n; i++) {int x = 0;for (int j = 1; j <= n; j++)if (!v[j] && (x == 0 || d[j] > d[x]))x = j;v[x] = true;for (int y = 1; y <= n; y++)if (!v[y])d[y] = max(pic[x][y], d[y]);}double sum = 0;for (int i = 2; i <= n; i++)sum += d[i];return sum >= 0;
}void solve() {double left = 0, right = 10, mid = 0;while (fabs(left - right) > 1e-4) {mid = (left + right) / 2;prim(mid) ? right : left = mid;}printf("%.3f\n", right);
}int main() {while (true) {scanf("%d", &n);if (!n)break;read();build();solve();}return 0;
}