最小生成树 + 01分数规划
好烦的卡精度题，调了一下午。。
题意大概就是给你一张稠密图，每条边都有收益和花费，要求一个花费之和与收益之和的比值和最小的生成树。
当然我们可以看成收益之和与花费之和的比值最大的生成树。。
这显然是一个01分数规划问题。然后二分枚举猜测的L值跑最大生成树就行了，若最大生成树大于等于0，代表我们的最大值大于等于L，于是mid = l，若最大生成树小于0，代表我们的最大值小于L， 于是mid = r。
#include#include #include #include #include #include #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)using namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){ int X = 0, w = 0; char ch = 0; while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); return w ? -X : X;}inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template inline T max(T x, T y, T z){ return max(max(x, y), z); }template inline T min(T x, T y, T z){ return min(min(x, y), z); }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 1005;const double eps = 1e-7;int n;double x[N], y[N], z[N];double dist[N][N], cost[N][N], cur[N][N], mst, d[N];bool vis[N];inline double getDis(double x1, double y1, double x2, double y2){ return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));}inline void build(double mid){ for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++) cur[i][j] = -INF; } for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ if(i == j) continue; cur[i][j] = dist[i][j] - mid * cost[i][j]; } }}inline void prim(){ for(int i = 1; i <= n; i ++){ d[i] = -INF; vis[i] = false; } d[1] = mst = 0.0; for(int i = 1; i < n; i ++){ int x = 0; for(int j = 1; j <= n; j ++){ if(!vis[j] && (x == 0 || d[j] > d[x])) x = j; } vis[x] = true; for(int j = 1; j <= n; j ++){ if(!vis[j]) d[j] = max(d[j], cur[x][j]); } } for(int i = 2; i <= n; i ++) mst += d[i];}inline bool check(){ prim(); return mst >= 0.0;}int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); while(cin >> n && n){ for(int i = 1; i <= n; i ++) cin >> x[i] >> y[i] >> z[i]; for(int i = 1; i <= n; i ++){ for(int j = i + 1; j <= n; j ++){ dist[i][j] = dist[j][i] = getDis(x[i], y[i], x[j], y[j]); cost[i][j] = cost[j][i] = fabs(z[i] - z[j]); } } double l = 0.0, r = 40.0; while(r - l >= eps){ double mid = (l + r) / 2; build(mid); if(check()) l = mid; else r = mid; } printf("%.3lf\n", 1 / l); } return 0;}