給你n個城市 每個城市有一定數量的人 連接2個城市需要的花費是他們之間的距離 現在要建一顆最小生成樹 可以免費建其中一條邊 設A為免費的那條邊連接的2個城市的人口之和 B為修建的最小生成樹的花費 求最大的A/B
先求最小生成樹 設總花費為totol 然後可以枚舉免費的那條邊 枚舉邊等於A確定 在這條在最小生成樹裡的情況下 求最小的B
如果這條邊是最小生成樹裡的邊 那麼很容易求得B 拿totol減去這條邊就行了
如果不是 那麼把這條邊加到最小生成樹 會出現一個環 找到這個環最大的那條邊剪掉 就是次小生成樹的做法 然後類似求A/B
n^2預處理任意2點之間唯一路徑上的最大邊權
#include#include #include #include #include using namespace std; const int maxn = 1010; struct poit { double x, y, p; }p[maxn]; struct edge { double dis; int u, v, next; bool select; }e[maxn*maxn], G[maxn*2]; struct node { double dis; int u, v; node(){} node(int u, int v, double d): u(u), v(v), dis(d) {} }; int n; double dp[maxn][maxn], totol; int f[maxn]; int first[maxn], cnt; void AddEdge(int u, int v, double w) { G[cnt].u = u; G[cnt].v = v; G[cnt].dis = w; G[cnt].next = first[u]; first[u] = cnt++; G[cnt].u = v; G[cnt].v = u; G[cnt].dis = w; G[cnt].next = first[v]; first[v] = cnt++; } void init() { for(int i = 1; i <= n; i++) f[i] = i; totol = 0; memset(dp, 0, sizeof(dp)); memset(first, -1, sizeof(first)); cnt = 0; } int find(int x) { if(x != f[x]) return f[x] = find(f[x]); return f[x]; } double Dist(int i, int j) { return sqrt((double)(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)); } bool cmp(edge a, edge b) { return a.dis < b.dis; } void MST(int l) { for(int i = 0; i < l; i++) { int x = find(e[i].u); int y = find(e[i].v); if(x != y) { totol += e[i].dis; f[x] = y; e[i].select = true; AddEdge(e[i].u, e[i].v, e[i].dis); } } } void BFS(int x) { queue Q; Q.push(node(-1, x, 0)); while(!Q.empty()) { node u = Q.front(); Q.pop(); for(int i = first[u.v]; i != -1; i = G[i].next) { if(G[i].v == u.u) continue; double temp = max(u.dis, G[i].dis); dp[x][G[i].v] = max(dp[x][G[i].v], temp); Q.push(node(u.v, G[i].v, temp)); } } } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &n); init(); for(int i = 1; i <= n; i++) scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].p); int l = 0; for(int i = 1; i <= n; i++) { for(int j = i+1; j <= n; j++) { if(i == j) continue; e[l].u = i; e[l].v = j; e[l].select = false; e[l].dis = Dist(i, j); l++; } } sort(e, e+l, cmp); MST(l); for(int i = 1; i <= n; i++) BFS(i); double ans = 0.0; for(int i = 0; i < l; i++) { int u = e[i].u, v = e[i].v; if(e[i].select) { double tmp = (p[u].p + p[v].p) / (totol-e[i].dis); ans = max(ans, tmp); } else { double tmp = (p[u].p + p[v].p) / (totol-dp[u][v]); ans = max(ans, tmp); } } printf("%.2lf\n", ans); } return 0; }
