重在思路
- 先求最小生成树,记录每一条边
- 然后枚举每一条边
- 删除这条后形成了两个连通块,分别求出出连通块的最多的人口城市
- 然后就按照这两个城市的值来更新答案
#include<bits/stdc++.h>
using namespace std;
const int PN = 1010;
double P_a[PN][PN], P_d[PN];
bool P_v[PN];
int dx[PN], dy[PN], p[PN], fa[PN],n;
//
const int N = 1010, M = 2010;
const double eps = 1e-8;
int head[N], ver[M], Next[M], tot;
double edge[M];
void add(int x, int y, double z) {
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
vector<pair<int, int>> vp;// 记录 n - 1 条边
void prim() {
for(int i = 2; i <= n; i++) P_d[i] = 2e9;
memset(P_v, 0, sizeof(P_v));
P_d[1] = 1e-5;
for (int i = 1; i < n; i++) {
int x = 0;
for (int j = 1; j <= n; j++)
if (!P_v[j] && (x == 0 || P_d[j] < P_d[x])) x = j;
P_v[x] = 1;
if(i != 1){
add(fa[x], x, P_a[fa[x]][x]);//边 fa[x] - x
add(x, fa[x], P_a[fa[x]][x]);
vp.push_back({x, fa[x]});
}
for (int y = 1; y <= n; y++)//记录一下从哪一个节点连到连通块
if (!P_v[y] && P_d[y] > P_a[x][y]) P_d[y] = P_a[x][y], fa[y] = x;
}
for (int x = 1; x <= n; x++)
if (!P_v[x]){
add(fa[x], x, P_a[fa[x]][x]);
add(x, fa[x], P_a[fa[x]][x]);
vp.push_back({x, fa[x]});
}
}
int main() {
int tt; cin >> tt;
while(tt--){
cin >> n;
memset(head, 0, sizeof head); tot = 1;
memset(P_a, 0x3f, sizeof(P_a));
vp.clear();
for (int i = 1; i <= n; i++) scanf("%d%d%d", dx + i, dy + i, p + i);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
P_a[i][j] = sqrt(pow(dx[i] - dx[j], 2) + pow(dy[i] - dy[j], 2));
prim();
double sum = 0;
for (int i = 2; i <= n; i++) sum += P_d[i];
double ans = eps;
for(auto [a1, a2] : vp){//枚举每一条边
int p1 = 0, p2 = 0;
function<void(int, int, int&)> dfs;
dfs = [&](int u, int f, int& pv){
pv = max(pv, p[u]);
for(int k = head[u]; k; k = Next[k])
if(ver[k] != f) dfs(ver[k], u, pv);
};
dfs(a1, a2, p1); dfs(a2, a1, p2);// p1 是 a1 所在连通块的最大人口的城市
ans = max(ans, (p1 + p2) / (sum - P_a[a1][a2]));//去掉这条边
}
printf("%.2lf\n", ans);
}
}
思路2
- 先求一个最小生成树
- 然后求一个cmax[][], cmax[i][j]代表在最小生成树中 i 到 j 的路径中的最大的一条边的长度
- 然后暴力枚举两端i,j设为端点,假设这个两个之间有一条路,又因为原本i,j之间有一条路,就会形成一个环,可以去掉环上的一条边,使其变为生成树,就是i 到 j的路径上的一条最大边cmax已经预处理过了
#include<bits/stdc++.h>
using namespace std;
const int PN = 1010;
double P_a[PN][PN], P_d[PN];
bool P_v[PN];
int dx[PN], dy[PN], p[PN], fa[PN], n;
//
const int N = 1010, M = 2010;
const double eps = 1e-8;
int head[N], ver[M], Next[M], tot;
void add(int x, int y) {ver[++tot] = y, Next[tot] = head[x], head[x] = tot;}
vector<pair<int, int>> vp;// 记录 n - 1 条边
void prim() {
for(int i = 2; i <= n; i++) P_d[i] = 2e9;
memset(P_v, 0, sizeof(P_v));
P_d[1] = 0;
for (int i = 1; i < n; i++) {
int x = 0;
for (int j = 1; j <= n; j++)
if (!P_v[j] && (x == 0 || P_d[j] < P_d[x])) x = j;
P_v[x] = 1;
if(i != 1) vp.push_back({x, fa[x]});
for (int y = 1; y <= n; y++)//记录一下从哪一个节点连到连通块
if (!P_v[y] && P_d[y] > P_a[x][y]) P_d[y] = P_a[x][y], fa[y] = x;
}
for (int x = 1; x <= n; x++)
if (!P_v[x]) {vp.push_back({x, fa[x]}); break;}
}
double cmax[N][N];
bitset<N> cv;
void dfs(int u, int f){
for(int i = 1; i <= n; i++)
if(cv[i]) cmax[i][u] = cmax[u][i] = max(cmax[i][f], P_a[f][u]);
cv[u] = 1;
for(int i = head[u]; i; i = Next[i])
if(ver[i] != f) dfs(ver[i], u);
}
int main() {
int tt; scanf("%d", &tt);
while(tt--){
scanf("%d", &n);
memset(head, 0, sizeof head); tot = 1;
vp.clear(), cv.reset();
for (int i = 1; i <= n; i++) scanf("%d%d%d", dx + i, dy + i, p + i);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
P_a[i][j] = sqrt(pow(dx[i] - dx[j], 2) + pow(dy[i] - dy[j], 2)),
cmax[i][j] = 0;
prim();
double sum = 0, ans = 0;
for (int i = 2; i <= n; i++) sum += P_d[i];
for(auto [a, b] : vp) add(a, b), add(b, a);
dfs(1, 0);
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
ans = max(ans, (p[i] + p[j]) / (sum - cmax[i][j]));
printf("%.2lf\n", ans);
}
}