(n100)
简单的分数规划+费用流
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const double inf=1e8,eps=1e-10;
const int N=104;
struct edge{
int v,nxt,f;
double c;
}e[N*N*2];
int first[N<<1],cur[N<<1],cnt,vis[N<<1],s,t;
double dis[N<<1],mon;
inline void clear(){
memset(first,0,sizeof(first));
cnt=1;mon=0;
}
inline void ADD(int u,int v,double c,int f){
e[++cnt].v=v;e[cnt].c=c;e[cnt].f=f;
e[cnt].nxt=first[u];first[u]=cnt;
}
inline void add(int u,int v,double c,int f){
ADD(u,v,c,f);
ADD(v,u,-c,0);
}
inline bool spfa(){
static queue<int>q;
for(int i=1;i<=t;i++)dis[i]=inf;
memset(vis,0,(t+1)<<2);
dis[t]=0;vis[t]=1;
q.push(t);
while(!q.empty()){
int x=q.front();q.pop();
vis[x]=0;
for(int i=first[x],v;i;i=e[i].nxt){
if(!e[i^1].f)continue;
v=e[i].v;
if(dis[v]>dis[x]-e[i].c){
dis[v]=dis[x]-e[i].c;
if(!vis[v]){q.push(v);vis[v]=1;}
}
}
}
return fabs(dis[s]-inf)>eps;
}
int dfs(int x,int f){
if(!f)return 0;
if(x==t){vis[0]=1;return f;}
vis[x]=1;
int used=0;
for(int &i=cur[x],v,w;i;i=e[i].nxt){
v=e[i].v;
if(vis[v]||fabs(dis[x]-dis[v]-e[i].c)>eps||!e[i].f)continue;
w=dfs(v,min(f,e[i].f));
if(!w)continue;
e[i].f-=w;e[i^1].f+=w;
used+=w;f-=w;
mon+=e[i].c*w;
if(!f)break;
}
return used;
}
inline void mcmf(){
while(spfa()){
memcpy(cur,first,(t+1)<<2);
vis[0]=1;
while(vis[0]){
memset(vis,0,(t+1)<<2);
dfs(s,inf);
}
}
}
int n,a[N][N],b[N][N];
int main(){
n=read();s=(n<<1)+1;t=s+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=read();
double l=0,r=10000,mid;
for(int i=1;i<=50;i++){
mid=(l+r)/2;
clear();
for(int j=1;j<=n;j++){
add(s,j,0,1);
add(j+n,t,0,1);
}
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++){
add(u,v+n,mid*b[u][v]-a[u][v],1);
}
mcmf();
if(mon<=0)l=mid;
else r=mid;
}
printf("%.6lf",r);
return (0-0);
}