单纯用分数规划

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
int n, vis[100][2];
struct node {
	double a, b;
	int  i, j;
} p[10001];
double l, r, mid;
bool cmp(node a, node b) {
	return (a.a * 1.00 - mid * a.b) > (b.a * 1.00 - mid * b.b);
}
int main() {
	cin >> n;
	rep(i, 1, n)
	rep(j, 1, n) {
		p[(i - 1)*n + (j - 1) + 1].i = i;
		p[(i - 1)*n + (j - 1) + 1].j = j;

	}
	rep(i, 1, n) rep(j, 1, n) cin >> p[(i - 1)*n + (j - 1) + 1].a;
	rep(i, 1, n) rep(j, 1, n) cin >> p[(i - 1)*n + (j - 1) + 1].b;
	l = -2e9, r = 2e9;
	while (r - l >= 1e-10) {
		mid = (l + r) / 2;
		sort(p + 1, p + 1 + n * n, cmp);
		memset(vis, 0, sizeof vis);
		double f = 0;
		for (int i = 1; i <= n * n; i++) {
			if (vis[p[i].i][0] || vis[p[i].j][1]) continue;
			f += (p[i].a * 1.00 - mid * p[i].b * 1.00);
			vis[p[i].i][0] = vis[p[i].j][1] = 1;
		}
		if (f >=0) l = mid;
		else r = mid;
	}
	printf("%.6lf", r+0.999);
}