感觉这道题和hdu4756很像...
求最小生成树里面删去一边E1 再加一边E2 求该边两顶点权值和除以（最小生成树-E1）的最大值
其中（最小生成树-E1）必须是最小的
先跑一遍prim 跑完之后在最小生成树里面dp
dp[i][j] = i到j的路径中最大的那条边 最小生成树减去dp[i][j]肯定会最小
代码如下
#include#include #include #include using namespace std;const double inf = 0x3f3f3f3f3f;const int maxn = 1010;struct Point { double x, y; int n;} point[maxn];struct Edge { int to; int next;} edge[maxn<<1];int n, cnt, head[maxn], pre[maxn];double dis[maxn][maxn], lowc[maxn], sum, dp[maxn][maxn];bool vis[maxn];inline void addedge(int u, int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++;}inline double Distance(const Point& lhs, const Point& rhs) { return sqrt((lhs.x - rhs.x) * (lhs.x - rhs.x) + (lhs.y - rhs.y) * (lhs.y - rhs.y));}void prim() { sum = 0.0; memset(vis, 0, sizeof(vis)); memset(pre, 0, sizeof(pre)); for (int i = 1; i < n; i++) lowc[i] = dis[0][i]; vis[0] = true; for (int i = 1; i < n; i++) { double minc = inf; int p = -1; for (int j = 0; j < n; j++) { if (!vis[j] && minc > lowc[j]) { minc = lowc[j]; p = j; } } sum += minc; vis[p] = true; addedge(p, pre[p]); addedge(pre[p], p); for (int j = 0; j < n; j++) { if (!vis[j] && lowc[j] > dis[p][j]) { lowc[j] = dis[p][j]; pre[j] = p; } } }}void dfs(int u, int root) { vis[u] = true; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (!vis[v]) { dp[root][v] = max(dp[root][u], dis[u][v]); dfs(v, root); } }}int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lf%lf%d", &point[i].x, &point[i].y, &point[i].n); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { dis[i][j] = dis[j][i] = Distance(point[i], point[j]); } } memset(head, -1, sizeof(head)); cnt = 0; prim(); for (int i = 0; i < n; i++) { memset(vis, 0,sizeof(vis)); dfs(i, i); } double ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double temp = sum - dp[i][j]; temp = (point[i].n + point[j].n) / temp; ans = max(ans, temp); } } printf("%.2f\n", ans); } return 0;}