【BZOJ4819】新生舞会（01分数规划,费用流）-白红宇

【BZOJ4819】新生舞会（01分数规划,费用流）

阅读量：6255 次

发布时间：2019-06-22

本文共 1632 字，大约阅读时间需要 5 分钟。

Solution

考虑一下这个东西的模型转换：

\(\frac{\sum_{i=1}^n{a_i}}{\sum_{i=1}^n{b_i}}\)

然后转换一下发现显然是01分数规划。

\(\sum_{i=1}^n{b_i}*mid\leq \sum_{i=1}^n{a_i}\)

然后再移项：

\(0 \leq \sum_{i=1}^n{a_i-b_i*mid}\)

然后就是求一个最大费用最大流判断是不是>0就好了。

~~口胡简单，实现靠自己~~

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=210;const double eps=1e-10,Inf=1e18;int front[N],to[(N*N)<<2],nxt[(N*N)<<2],w[(N*N)<<2],s=0,t,cnt,vis[N<<2],fa[N<<2],pre[N<<2],n,a[N][N],b[N][N];double c[(N*N)<<2],dis[N<<2];void Add(int u,int v,int val,double f){ to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;c[cnt++]=f; to[cnt]=u;nxt[cnt]=front[v];front[v]=cnt;w[cnt]=0;c[cnt++]=-f;}queue
             
              Q;bool SPFA(){ for(int i=s;i<=t+1;i++)dis[i]=-Inf; dis[s]=0; Q.push(s); while(!Q.empty()){ int u=Q.front();Q.pop();vis[u]=0; for(int i=front[u];i!=-1;i=nxt[i]){ int v=to[i]; if(w[i] && dis[v]
              
               =0)return true; return false;}int main(){ n=gi();t=n+n+1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=gi(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) b[i][j]=gi(); double l=0,r=10000; while(r-l>eps){ double mid=l+(r-l)*0.5; if(check(mid))l=mid; else r=mid; } printf("%.6lf\n",l); return 0;}