分数规划的裸题。
不会分数规划的OIer。百度：胡伯涛《最小割模型在信息学竞赛中的应用》
/* TLE1: last:add(i,j+n,1e9,(real)((real)a[i][j]-ans*(real)b[i][j])); now :add(i,j+n,1,(real)((real)a[i][j]-ans*(real)b[i][j])); TLE2: last:real l=eps,r=(real)u/(real)v,mid,ans=0,now; now :real l=0,r=(real)(u+v-1)/(real)v,mid,ans=0,now; TLE3: last:struct edge{int v,next;real cost,cap;}e[N<<1]; now :to[N],next[N],cap[N];real cost[N];(结构体跑得慢) TLE4： last:typedef long double real; now :typedef double real; */ #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout); using namespace std; const int N=1e5+5; const int Z=105; typedef long double real; const real eps=1e-8; int n,m,S,T,a[Z][Z],b[Z][Z]; int to[N],next[N],cap[N];real cost[N];int tot=1,head[N]; real dis[N];int q[N],pre[N];bool vis[N]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void add(int x,int y,int z,real Cost){ to[++tot]=y;cap[tot]=z;cost[tot]=Cost;next[tot]=head[x];head[x]=tot; to[++tot]=x;cap[tot]=0;cost[tot]=-Cost;next[tot]=head[y];head[y]=tot; } bool spfa(){ memset(vis,0,sizeof vis); for(int i=0;i<=T+10;i++) dis[i]=-1e9; unsigned short h=0,t=1;q[t]=S;dis[S]=0; while(h!=t){ int x=q[++h];vis[x]=0; for(int i=head[x];i;i=next[i]){ if(cap[i]>0&&dis[to[i]]<dis[x]+cost[i]){ dis[to[i]]=dis[x]+cost[i]; pre[to[i]]=i; if(!vis[to[i]]){ vis[to[i]]=1; q[++t]=to[i]; } } } } return dis[T]>-1e9; } real augment(){ // int flow=1e9; // for(int i=T;i!=S;i=to[pre[i]^1]) flow=min(flow,cap[pre[i]]); int flow=1; for(int i=T;i!=S;i=to[pre[i]^1]){ cap[pre[i]]-=flow; cap[pre[i]^1]+=flow; } return dis[T]*flow; } real mapping(real ans){ tot=1;S=0;T=n<<1|1; memset(head,0,sizeof head); 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,(real)((real)a[i][j]-ans*(real)b[i][j])); } } real res=0.0; while(spfa()) res+=augment(); return res; } int cmp(real x){ if(fabs(x)<eps) return 0; return x>0?1:-1; } void work1(){ tot=1;S=0;T=n<<1|1; memset(head,0,sizeof head); 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,(real)a[i][j]); } } real res=0.0; while(spfa()) res+=augment(); res/=1.0*n; printf("%.6lf ",(double)res); } int main(){ set(ball); n=read(); int u=0,v=0; for(int i=1,t;i<=n;i++){ t=0; for(int j=1;j<=n;j++){ a[i][j]=read(); t=max(t,a[i][j]); } u+=t; } bool f=1; for(int i=1,t;i<=n;i++){ t=1e9; for(int j=1;j<=n;j++){ b[i][j]=read(); t=min(t,b[i][j]); if(b[i][j]!=1) f=0; } v+=t; } if(f){work1();return 0;} real l=0,r=(real)(u+v-1)/(real)v,mid,ans=0,now; while(l+eps<r){ mid=(l+r)/2.0; now=mapping(mid); if(cmp(now)==0){printf("%.6lf ",(double)mid);return 0;} if(cmp(now)>0) l=mid; else r=mid; } printf("%.6lf ",(double)l); fclose(stdin); fclose(stdout); return 0; }