bzoj 3232: 圈地游戏

---

01分数规划，就是你要最大化\(\frac{\sum A}{\sum B}\)，就二分这个值，\(\frac{\sum A}{\sum B} \geq mid\)

\(\sum A-mid\sum B \geq 0\)

然后把所有的B中的权值乘一个mid再跑一个什么算法就星了

这就是道裸题（雾）

二分一个\(mid\)，就是一个网络流问题了

选一个点的集合，如果两个方格相邻，一个选了一个没选，总和就要减去中间这条边的权值

然后用最小鸽，如果选就没有损失，不选有格子上价值的损失；两个相邻点一个选了一个不选有中间那条边边权*mid的损失，裸的最小鸽

还有边界上的边怎么办，就边界外面新建一圈点，强制那些点不选。就做完了。

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    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;

}

const double inf=1e9;

int n,m,val[51][51],wh[51][51],ww[51][51];

int dep[3000],fir[3000],head[3000],dis[1000010],nxt[1000010],id;

double w[1000010];

il vd link(int a,int b,double c,double d=0){

    nxt[++id]=head[a],head[a]=id,dis[id]=b,w[id]=c;

    nxt[++id]=head[b],head[b]=id,dis[id]=a,w[id]=d;

}

int num[52][52],NUM_ID,S,T;

il bool BFS(){

    static int que[3000],hd,tl;

    hd=tl=0;

    que[tl++]=S;for(int i=1;i<=NUM_ID;++i)dep[i]=0;dep[S]=1;

    while(hd^tl){

        int x=que[hd];

        for(int i=head[x];i;i=nxt[i])

            if(w[i]>1e-7&&!dep[dis[i]])dep[dis[i]]=dep[x]+1,que[tl++]=dis[i];

        ++hd;

    }

    return dep[T];

}

il double Dinic(int x,double maxflow){

    if(x==T)return maxflow;

    double ret=0;

    for(int&i=fir[x];i;i=nxt[i])

        if(w[i]>1e-7&&dep[dis[i]]==dep[x]+1){

            double d=Dinic(dis[i],std::min(maxflow,w[i]));

            w[i]-=d,w[i^1]+=d;ret+=d,maxflow-=d;

            if(maxflow<1e-7)return ret;

        }

    return ret;

}

il double check(double mid){

    memset(head,0,sizeof head);id=1;

    for(int i=1;i<=m;++i)link(S,num[0][i],inf),link(S,num[n+1][i],inf);

    for(int i=1;i<=n;++i)link(S,num[i][0],inf),link(S,num[i][m+1],inf);

    double ret=0;

    for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j)

            link(num[i][j],T,val[i][j]),ret+=val[i][j];

    for(int i=1;i<=n+1;++i)

        for(int j=1;j<=m;++j)

            link(num[i-1][j],num[i][j],mid*wh[i][j],mid*wh[i][j]);

    for(int i=1;i<=n;++i)

        for(int j=1;j<=m+1;++j)

            link(num[i][j-1],num[i][j],mid*ww[i][j],mid*ww[i][j]);

    while(BFS())memcpy(fir,head,sizeof fir),ret-=Dinic(S,inf);

    return ret;

}

int main(){

    n=gi(),m=gi();

    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)val[i][j]=gi();

    for(int i=1;i<=n+1;++i)for(int j=1;j<=m;++j)wh[i][j]=gi();

    for(int i=1;i<=n;++i)for(int j=1;j<=m+1;++j)ww[i][j]=gi();

    for(int i=0;i<=n+1;++i)

        for(int j=0;j<=m+1;++j)

            num[i][j]=++NUM_ID;

    S=++NUM_ID,T=++NUM_ID;

    double l=0,r=5000,mid;

    while(r-l>1e-6){

        mid=(l+r)/2;

        if(check(mid)>1e-7)l=mid;

        else r=mid;

    }

    printf("%.3lf\n",l);

    return 0;

}