考虑分数规划。
二分一个 \(mid\)，令 \(c_{i,j}=a_{i,j}-mid\cdot b_{i,j}\)，那么现在要找一个 \([1,n]\rightarrow[1,n]\) 的双射 \(f\)，使得 \(c_{i,f_i}\) 之和最大。
直接使用km费用流。
代码
没写 \(double\),把每个数乘了 \(1000000\)，变成 \(long long\)
/*
Luogu P3705 [SDOI2017] 新生舞会
2026-04-08
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
#define LL long long
const int maxn=110;
const LL inf=10000000000000000;
const double eps=1e-8;
int n,a[maxn][maxn],b[maxn][maxn];
LL c[maxn][maxn];
template<int maxn,int maxm>struct LSQXX{int head[maxn],nxt[maxm*2],to[maxm*2],val[maxm*2],cnt=1;LL cost[maxm*2];void add(int u,int v,int z,LL c){nxt[++cnt]=head[u],to[cnt]=v,val[cnt]=z,cost[cnt]=c,head[u]=cnt;}void clear(){memset(head,0,sizeof(head)),cnt=1;}
};
class Network_Flow{
private:LSQXX<maxn*2,maxn*maxn>e;int cur[maxn*2],s,t;LL ans2,dis[maxn*2];bool inque[maxn*2],vis[maxn*2];void edge_add(int u,int v,int w,LL z){e.add(u,v,w,-z),e.add(v,u,0,z);}bool spfa(){for(int i=s;i<=t;i++) inque[i]=0,dis[i]=inf;queue<int>q;q.push(s);dis[s]=0;while(!q.empty()){int u=q.front();q.pop();inque[u]=0;for(int i=e.head[u];i;i=e.nxt[i]){int v=e.to[i];if(e.val[i]==0) continue;if(dis[v]>dis[u]+e.cost[i]){dis[v]=dis[u]+e.cost[i];if(!inque[v]) q.push(v),inque[v]=1;}}}return dis[t]!=inf;}int dfs(int u,int flow=100){if(flow==0||u==t) return flow;int ans=0;if(vis[u]) return 0;vis[u]=1;for(int&i=cur[u];i;i=e.nxt[i]){int v=e.to[i];if(dis[v]!=dis[u]+e.cost[i]) continue;int new_flow=dfs(v,min(flow,e.val[i]));flow-=new_flow,ans+=new_flow,ans2+=new_flow*e.cost[i];e.val[i]-=new_flow,e.val[i^1]+=new_flow;if(flow==0) return vis[u]=0,ans;}vis[u]=0;return ans;}
public:void build(double mid){s=0,t=n*2+1;e.clear();for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){double z=a[i][j]-b[i][j]*mid;c[i][j]=z*1000000;}for(int i=1;i<=n;i++) edge_add(s,i,1,0),edge_add(i+n,t,1,0);for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) edge_add(i,j+n,1,c[i][j]);}LL work(){ans2=0;while(spfa()){for(int i=s;i<=t;i++) cur[i]=e.head[i];dfs(s);}return -ans2;}
}wll;
signed main(){read(n);for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(a[i][j]);for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(b[i][j]);double l=0,r=1000000,ans=0;while(l+eps<r){double mid=(l+r)/2;wll.build(mid);if(wll.work()>=0) l=mid+eps,ans=mid;else r=mid-eps;}printf("%.6lf",ans);return 0;
}