【题意】：给出n(n<=1000)个城市的坐标和城市的居住人口，要求修n-1条路使得n个城市连通，修路的代价就是路长，并且允许免费修一条路。问：被免费的路所连接的两个城市人口之和比上修路的代价（这里是n-2条路的代价之和，因为有一条路是免费的)的最大值是多少。
【题解】：这题是北京现场赛的A题，当时想到解法，可惜是O(n*n*n)的。
其实这题就是一道次小生成树变形，不过当时不会，现在学了，顺便切了它。
首先可以想到最小生成树，但是免费的路这个怎么处理，考虑到数据n<=1000，我们可以枚举两点之间的路。
如果该路已经在MST上，那么比值就是(cnt[u]+cnt[v]) / (MST - w(u, v))；
如果该路不在MST上，那么我们把这条路加上去的话肯定会形成一个环，为了保证比值最大，我们显然要删除环上第二大的边(第一大的边肯定是新添加的这条路，不能删除)，那么比值就是(cnt[u]+cnt[v]) / (MST - path[u][v]),其中path[i][j]表示在MST上节点i到节点j路径上的最大边。
复杂度O(n*n)。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 using namespace std;
11 #define pb push_back
12 #define lc(x) (x << 1)
13 #define rc(x) (x << 1 | 1)
14 #define lowbit(x) (x & (-x))
15 #define ll long long
16 #define maxn 1005
17 const double dinf = 1e10;
18 const int inf = 1 << 30;
19 int n, m;
20 int pre[maxn], stack[2*maxn], top;
21 double maz[maxn][maxn], dist[maxn], path[maxn][maxn];
22 bool visit[maxn];
23 struct Point {
24 double x, y;
25 int cnt;
26 }p[maxn];
27
28 double getdist(const Point &a, const Point &b) {
29 return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
30 }
31
32 double prim(int s) {
33 double ans = 0;
34 for(int i = 0; i < n; i++) visit[i] = false, dist[i] = dinf, pre[i] = s;
35 dist[s] = 0, top = 0;
36 while(1) {
37 int u = -1;
38 for(int i = 0; i < n; i++) {
39 if(!visit[i] && (u == -1 || dist[i] < dist[u])) u = i;
40 }
41 if(u == -1) break;
42 stack[top++] = u, visit[u] = true;
43 ans += dist[u];
44 for(int i = 0; i < top; i++) {
45 if(stack[i] == u) continue;
46 path[stack[i]][u] = max(path[stack[i]][pre[u]], dist[u]);
47 path[u][stack[i]] = path[stack[i]][u];
48 }
49 for(int i = 0; i < n; i++) {
50 if(!visit[i] && maz[u][i] < dist[i])
51 dist[i] = maz[u][i], pre[i] = u;
52 }
53 }
54 return ans;
55 }
56
57 void solve() {
58 double MST = prim(0), ans = 0.0;
59 for(int i = 0; i < n; i++) {
60 for(int j = 0; j < n; j++) {
61 if(i == j) continue;
62 if((pre[i] == j || pre[j] == i)) ans = max(ans, (p[i].cnt + p[j].cnt) / (MST - maz[i][j]));
63 else ans = max(ans, (p[i].cnt + p[j].cnt) / (MST - path[i][j]));
64 }
65 }
66 printf("%.2f\n", ans);
67 }
68
69 int main() {
70 int T;
71 scanf("%d", &T);
72 while(T--) {
73 scanf("%d", &n);
74 for(int i = 0; i < n; i++) {
75 scanf("%lf%lf%d", &p[i].x, &p[i].y, &p[i].cnt);
76 }
77 for(int i = 0; i < n; i++) {
78 for(int j = 0; j < n; j++) {
79 maz[i][j] = getdist(p[i], p[j]);
80 path[i][j] = 0.0;
81 }
82 }
83 solve();
84 }
85 return 0;
86 }