【題意】：給出n(n<=1000)個(gè)城市的坐標(biāo)和城市的居住人口，要求修n-1條路使得n個(gè)城市連通，修路的代價(jià)就是路長(zhǎng)，并且允許免費(fèi)修一條路。問(wèn)：被免費(fèi)的路所連接的兩個(gè)城市人口之和比上修路的代價(jià)（這里是n-2條路的代價(jià)之和，因?yàn)橛幸粭l路是免費(fèi)的)的最大值是多少。
【題解】：這題是北京現(xiàn)場(chǎng)賽的A題，當(dāng)時(shí)想到解法，可惜是O(n*n*n)的。
其實(shí)這題就是一道次小生成樹變形，不過(guò)當(dāng)時(shí)不會(huì)，現(xiàn)在學(xué)了，順便切了它。
首先可以想到最小生成樹，但是免費(fèi)的路這個(gè)怎么處理，考慮到數(shù)據(jù)n<=1000，我們可以枚舉兩點(diǎn)之間的路。
如果該路已經(jīng)在MST上，那么比值就是(cnt[u]+cnt[v]) / (MST - w(u, v))；
如果該路不在MST上，那么我們把這條路加上去的話肯定會(huì)形成一個(gè)環(huán)，為了保證比值最大，我們顯然要?jiǎng)h除環(huán)上第二大的邊(第一大的邊肯定是新添加的這條路，不能刪除)，那么比值就是(cnt[u]+cnt[v]) / (MST - path[u][v]),其中path[i][j]表示在MST上節(jié)點(diǎn)i到節(jié)點(diǎn)j路徑上的最大邊。
復(fù)雜度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 }