/* 01分数规划，二分答案k，看是否存在方案使的(a1+a2+a3...)/(b1+b2+b3...)>=k。 即(a1-k*b1)+(a2-k*b2)+(a3-k*b3)...>=0，那么用费用流写就行了。 需要注意的是常数问题没需要用一点黑科技，比如把结构体改成数组。 */ #include<iostream> #include<cstdio> #include<queue> #include<cstring> #define N 210 #define M 40100 #define eps 0.0000001 #define inf 1000000000 using namespace std; int a[N][N],b[N][N],n; int head[N],inq[N],fa[N],S,T,cnt=1; int to[M],f[M],pre[M]; double dis[N],w[M]; queue<int> q; void add(int u,int v,int ff,double ww){ to[++cnt]=v;pre[cnt]=head[u];f[cnt]=ff;w[cnt]=ww;head[u]=cnt; to[++cnt]=u;pre[cnt]=head[v];f[cnt]=0;w[cnt]=-ww;head[v]=cnt; } bool spfa(){ for(int i=0;i<=T;i++) dis[i]=-inf; dis[S]=0;q.push(S); while(!q.empty()){ int u=q.front();q.pop();inq[u]=0; for(int i=head[u];i;i=pre[i]) if(f[i]>0&&dis[to[i]]<dis[u]+w[i]){ dis[to[i]]=dis[u]+w[i]; fa[to[i]]=i; if(!inq[to[i]]) q.push(to[i]),inq[to[i]]=1; } } return dis[T]!=-inf; } double up_data(){ int tmp=fa[T]; while(tmp){ f[tmp]--; f[tmp^1]++; tmp=fa[to[tmp^1]]; } return dis[T]; } double work(double k){ memset(head,0,sizeof(head)); S=0;T=n*2+1;cnt=1; for(int i=1;i<=n;i++) add(S,i,1,0),add(i+n,T,1,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) add(i,j+n,1,(double)a[i][j]-k*(double)b[i][j]); double maxv=0; while(spfa()){ if(maxv<0) return maxv; maxv+=up_data(); } return maxv; } int main(){ scanf("%d",&n);int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]),sum+=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=(double)sum/(double)n; while(r-l>eps){ double mid=(l+r)/2.0; if(work(mid)>0) l=mid; else r=mid; } printf("%.6lf",(l+r)/2.0); return 0; }