01规划

 

a1+a2+a3+...+ai/b1+b2+b2+..bi最大

 

设一个k

使得

　　a1+a2+a3+...+ai/b1+b2+b3+...bi>=k

 

变换式子得到

　　a1+a2+a3+...ai>=(b1+b2+b3+..+bi)*k

　　a1-b1*k+a2-b2*k+a3-b3*k+...+ai-bi*k>=0

 

　　ai-bi*k即流量

　　最大费用流+二分答案

 

来，上代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define eps 1e-8#define maxn 205int ai[maxn][maxn],bi[maxn][maxn],ma,mi,pre[maxn],s,t,h,tail,cnt;int n,head[maxn],E[maxn*maxn],V[maxn*maxn],F[maxn*maxn],que[maxn<<8];double W[maxn*maxn],suma,sumb,dis[maxn];bool if_[maxn];inline void in(int &now_){    register int now=0;    register char Cget=getchar();    while(Cget>'9'||Cget<'0') Cget=getchar();    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }    now_=now;}inline bool spfa(){    for(int i=s;i<=t;i++) dis[i]=-1e6,pre[i]=-1,if_[i]=false;    h=maxn<<4,tail=h+1,que[h]=s,dis[s]=0,if_[s]=true;    while(h
        
         0)            {                pre[V[i]]=i;                dis[V[i]]=dis[now]+W[i];                if(!if_[V[i]])                {                    if_[V[i]]=true;                    if(dis[V[i]]>dis[que[h]]) que[--h]=V[i];                    else que[tail++]=V[i];                }            }        }    }    return dis[t]!=-1e6;}int main(){    freopen("ball.in","r",stdin);    freopen("ball.out","w",stdout);    in(n);t=n<<1|1;    for(register int i=1;i<=n;i++)    {        ma=0;        for(register int j=1;j<=n;j++) in(ai[i][j]),ma=max(ma,ai[i][j]);        suma+=ma;    }    for(register int i=1;i<=n;i++)    {        mi=0x7fffffff;        for(register int j=1;j<=n;j++) in(bi[i][j]),mi=min(mi,bi[i][j]);        sumb+=mi;    }    double l=0,r=suma/sumb,mid,ans;    while(r-l>eps)    {        mid=(l+r)/2.0,cnt=1;        for(register int i=s;i<=t;i++) head[i]=0;        for(register int i=1;i<=n;i++)        {            E[++cnt]=head[s],V[cnt]=i,F[cnt]=1,W[cnt]=0,head[s]=cnt;            E[++cnt]=head[i],V[cnt]=s,F[cnt]=0,W[cnt]=0,head[i]=cnt;            E[++cnt]=head[t],V[cnt]=i+n,F[cnt]=0,W[cnt]=0,head[t]=cnt;            E[++cnt]=head[i+n],V[cnt]=t,F[cnt]=1,W[cnt]=0,head[i+n]=cnt;            for(register int j=1;j<=n;j++)            {                register int o=j+n;                register double pos=(double)ai[i][j]-mid*bi[i][j];                E[++cnt]=head[i],V[cnt]=o,F[cnt]=1,W[cnt]=pos,head[i]=cnt;                E[++cnt]=head[o],V[cnt]=i,F[cnt]=0,W[cnt]=-pos,head[o]=cnt;            }        }        double sum=0;        while(spfa())        {            sum+=dis[t];            register int now=t;            while(pre[now]!=-1) F[pre[now]]--,F[pre[now]^1]++,now=V[pre[now]^1];        }        if(sum>0) ans=mid,l=mid+eps;        else r=mid-eps;    }    printf("%.6lf",ans);    fclose(stdin),fclose(stdout);    return 0;}