裸01分数规划。二分之后就是裸最大费用最大流了。

写的朴素SPFA费用流，洛谷跑的非常快啊，为什么有人还T成那样。。

当然用二分也很慢，用什么什么迭代会很快。

[Update] 19.2.15

下午写的zkw费用流在BZOJ上T了= =

然而在洛谷上和以前写的跑的差不多快

当然还可以写整数二分或者KM...

输出的时候最好加个eps，不然可以被卡比如里的数据。

---

第一次写的代码：

//3624kb    4016ms#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define gc() getchar()#define eps 1e-7#define INF 1e14const int N=205,M=90000;int n,src,des,Enum,H[N],to[M],fr[M],nxt[M],cap[M],pre[N];bool inq[N];double Ans,dis[N],A[N][N],B[N][N],cost[M];std::queue
         
           q;inline int read(){ int now=0;register char c=gc(); for(;!isdigit(c);c=gc()); for(;isdigit(c);now=now*10+c-'0',c=gc()); return now;}inline void AddEdge(int u,int v,int w,double c){ to[++Enum]=v, nxt[Enum]=H[u], fr[Enum]=u, H[u]=Enum, cap[Enum]=w, cost[Enum]=c; to[++Enum]=u, nxt[Enum]=H[v], fr[Enum]=v, H[v]=Enum, cap[Enum]=0, cost[Enum]=-c;}bool SPFA(){ for(int i=1; i<=des; ++i) dis[i]=-INF; q.push(src), dis[src]=0; while(!q.empty()) { int x=q.front();q.pop(); inq[x]=0; for(int v,i=H[x]; i; i=nxt[i]) if(dis[to[i]]
          
           -INF;}void MCMF(){ for(int i=des; i!=src; i=fr[pre[i]]) --cap[pre[i]], ++cap[pre[i]^1], Ans+=cost[pre[i]];}bool pre_Check(double C){ for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) /*if(i!=j) j是女生，不是自己。。*/ AddEdge(i,j+n,1,A[i][j]-C*B[i][j]); for(int i=1; i<=n; ++i) AddEdge(src,i,1,0),AddEdge(i+n,des,1,0); Ans=0; while(SPFA()){ MCMF(); if(Ans<0) break; } return Ans>=0;}bool Check(double C){ int cnt=1; for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) cap[++cnt]=1, cost[cnt]=A[i][j]-C*B[i][j], cap[++cnt]=0, cost[cnt]=-A[i][j]+C*B[i][j]; for(int i=1; i<=n; ++i) cap[++cnt]=1, cost[cnt]=0, cap[++cnt]=0, cost[cnt]=0, cap[++cnt]=1, cost[cnt]=0, cap[++cnt]=0, cost[cnt]=0; Ans=0; while(SPFA()){ MCMF(); if(Ans<0) break; } return Ans>=0;}int main(){ n=read(),Enum=1,src=0,des=n<<1|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.0,mid; if(pre_Check(mid=(l+r)*0.5)) l=mid; else r=mid; while(r>l+eps) if(Check(mid=(l+r)*0.5)) l=mid; else r=mid; printf("%.6lf",l+eps); return 0;}
          
         
        
       
      
     
    

第二次写的代码：（BZOJ上T掉的zkw= =）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define eps 1e-7#define gc() getchar()typedef long long LL;const int N=207,M=(N*N+N)*2;const double INF=1ll<<61;int T,Enum,cur[N],H[N],to[M],nxt[M],cap[M],A[103][103],B[103][103];bool vis[N];double Cost,cost[M],dis[N];inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-48,c=gc());    return now;}inline void AE(int u,int v){    to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;    to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;}void PreBuild(int n){    Enum=1;    for(int i=1; i<=n; ++i)        for(int j=1; j<=n; ++j) AE(i,j+n);    for(int i=1; i<=n; ++i) AE(0,i), AE(i+n,T);}bool BFS(){    static bool inq[N];    static std::queue
         
           q; for(int i=1; i<=T; ++i) dis[i]=-INF; q.push(0), dis[0]=0; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; for(int i=H[x],v; i; i=nxt[i]) if(dis[v=to[i]]
          
           -INF;}bool DFS(int x){ if(x==T) return 1; vis[x]=1;//!! for(int &i=cur[x]; i; i=nxt[i]) if(!vis[to[i]] && cap[i] && dis[to[i]]==dis[x]+cost[i] && DFS(to[i])) return --cap[i], ++cap[i^1], Cost+=cost[i], 1; return 0;}bool MCMF(){ Cost=0; while(BFS()) { memset(vis,0,T+1), memcpy(cur,H,T+1<<2); while(DFS(0) && Cost>=0); if(Cost<0) break; } return Cost>=0;}bool Check(int n,double x){ int now=1; for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) cap[++now]=1, cost[now]=A[i][j]-x*B[i][j], cap[++now]=0, cost[now]=-cost[now-1]; for(int i=1; i<=n; ++i) cap[++now]=1, cap[++now]=0, cap[++now]=1, cap[++now]=0; return MCMF();}int main(){ freopen("ball.in","r",stdin); freopen("ball.out","w",stdout); int n=read(); T=n+n+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(); PreBuild(n); double l=0,r=1e4+1e-4,mid; while(l+eps