Description：

给出 $a[i][j]$ 和 $b[i][j]$ ，把所有两两配对最小化 $\frac{a[p11][p12]+a[p21][p22]+\cdots+a[pk1][pk2]}{b[p11][p12]+b[p21][p22]+\cdots+b[pk1][pk2]}$ 。

$1\leqslant n \leqslant 100$

Solution：

$01$ 分数规划，先二分一个 $k$ ，然后设 $s[i][j]=a[i][j]-k\times b[i][j]$ ，按 $s[i][j]$ 求二分图最大权匹配判一下是否大于零，如果小于零，说明大了，否则说明小了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

#define MAXN 210

int a[MAXN][MAXN],b[MAXN][MAXN];

const double eps = 1e-8;

struct edge

{

	int to,nxt,f;

	double c;

}e[MAXN * MAXN + MAXN * 2];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int f,double c)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].c =  c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].c = -c;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int s,t;

void build(double k)

{

	s = 2 * n + 1;t = s + 1;

	memset(lin,-1,sizeof(lin));edgenum = 0;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= n;++j)

			add(i,j + n,1,a[i][j] - k * b[i][j]);

	for(int i = 1;i <= n;++i)

		add(s,i,1,0),add(i + n,t,1,0);

	return;

}

double d[MAXN];

int pre[MAXN],rate[MAXN];

bool inq[MAXN];

#define INF 0x3f3f3f3f

bool equal(double a,double b){return fabs(a - b) < eps;}

bool SPFA()

{

	rate[s] = INF;

	for(int i = 1;i <= t;++i)d[i] = -1000000000000;

	queue<int> q;q.push(s);d[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] < d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				pre[e[i].to] = i;rate[e[i].to] = min(rate[k],e[i].f);

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}//cout << d[t] << endl;

	return !equal(d[t],-1000000000000);

}

double flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return d[t] * rate[t];

}

double EK()

{

	double ans = 0;

	while(SPFA())ans += flow();

	return ans;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= n;++j)

			scanf("%d",&a[i][j]);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= n;++j)

			scanf("%d",&b[i][j]);

	double l = 0,r = 10000000,mid;

	while(r - l > eps)

	{

		mid = (l + r) / 2;

		build(mid);

		if(EK() < 0)r = mid;

		else l = mid;

	}

	printf("%.6lf\n",l);

	return 0;

}