bzoj 3232 圈地游戏——0/1分数规划(或网络流)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3232

当然是0/1分数规划。但加的东西和减的东西不在一起，怎么办？

考虑把它们合在一起。因为边围成的形状像一个环，所以把格子的贡献也放到边上，然后正常判环。

放到边上的方法就是：比如竖着的边，可以在每一行上维护该行格子值前缀和，然后指定那个围成的形状是，比如，逆时针的，那么向上的边就加上到它为止的前缀值，向下的边就减去到它为止的前缀值，然后就能判环了！

这样一定只有一个环。但多个环答案不会更优。

还可以用网络流。与 s 相连表示选、与 t 相连表示不选的话，每个点到 s 连该点权值的边，到 t 连边权为0的边，相邻点之间连它们夹着的边权值的边，这样如果相邻的点一个选了一个没选，就得割它们之间的那条边，就能表示了。

自己写了判环的那个。

注意如果以竖着的边算了围住的部分，就不要再用横着的边同时算了！！

请把 eps 设成 1e-7 而不是 1e-5 。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define db double

using namespace std;

const int N=,M=N*N;

const db eps=1e-;

int n,m,fl[N][N]/*,fu[N][N]*/,eh[N][N],el[N][N],cnt[N][N],tot;

db l,r,mid,ans,dis[N][N],w[N][N][];

bool vis[N][N];

queue<pair<int,int> > q;

bool spfa()

{

//    printf("mid=%.3lf\n",mid);

    while(q.size())q.pop();

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

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

        {

            q.push(make_pair(i,j));

            vis[i][j]=; dis[i][j]=; cnt[i][j]=;

            if(i)

            {

                w[i][j][]=fl[i][j]-mid*el[i][j];

//                if(mid<3&&mid>2&&el[i][j]==1)

//                printf("w[%d][%d][0]=%.3lf\n",i,j,w[i][j][0]);

            }

            if(j)

            {

                w[i][j][]=/*-fu[i][j]*/-mid*eh[i][j];

//                if(mid<3&&mid>2&&eh[i][j]==1)

//                printf("w[%d][%d][1]=%.3lf\n",i,j,w[i][j][1]);

            }

            if(i<n)

            {

                w[i][j][]=-fl[i+][j]-mid*el[i+][j];

//                if(mid<3&&mid>2&&el[i+1][j]==1)

//                printf("w[%d][%d][3]=%.3lf\n",i,j,w[i][j][3]);

            }

            if(j<m)

            {

                w[i][j][]=/*fu[i][j+1]*/-mid*eh[i][j+];

//                if(mid<3&&mid>2&&eh[i][j+1]==1)

//                printf("w[%d][%d][2]=%.3lf\n",i,j,w[i][j][2]);

            }

        }

    while(q.size())

    {

        int x=q.front().first,y=q.front().second;

        q.pop();

        vis[x][y]=;

//        if(mid>2&&mid<3)printf("x=%d y=%d cnt=%d dis=%.3lf\n",x,y,cnt[x][y],dis[x][y]);

//        if(mid>2&&mid<3)printf("fa[%d][%d]=(%d,%d)\n",x,y,fa[x][y][0],fa[x][y][1]);

        if(x&&dis[x-][y]<dis[x][y]+w[x][y][])

        {

            dis[x-][y]=dis[x][y]+w[x][y][];

//            printf("  w[%d][%d][0]=%.3lf\n",x,y,w[x][y][0]);

//            fa[x-1][y][0]=x; fa[x-1][y][1]=y;

            cnt[x-][y]=cnt[x][y]+;

            if(cnt[x-][y]==tot)

            {

//                if(mid>2&&mid<3)

//                    printf("x-1=%d y=%d dis=%.3lf\n",x-1,y,dis[x-1][y]);

                return ;

            }

            if(!vis[x-][y])

                vis[x-][y]=,q.push(make_pair(x-,y));

        }

        if(y&&dis[x][y-]<dis[x][y]+w[x][y][])

        {

            dis[x][y-]=dis[x][y]+w[x][y][];

//            printf("  w[%d][%d][1]=%.3lf\n",x,y,w[x][y][1]);

//            fa[x][y-1][0]=x; fa[x][y-1][1]=y;

            cnt[x][y-]=cnt[x][y]+;

            if(cnt[x][y-]==tot)

            {

//                if(mid>2&&mid<3)

//                    printf("x=%d y-1=%d dis=%.3lf\n",x,y-1,dis[x][y-1]);

                return ;

            }

            if(!vis[x][y-])

                vis[x][y-]=,q.push(make_pair(x,y-));

        }

        if(x<n&&dis[x+][y]<dis[x][y]+w[x][y][])

        {

            dis[x+][y]=dis[x][y]+w[x][y][];

//            printf("  w[%d][%d][3]=%.3lf\n",x,y,w[x][y][3]);

//            fa[x+1][y][0]=x; fa[x+1][y][1]=y;

            cnt[x+][y]=cnt[x][y]+;

            if(cnt[x+][y]==tot)

            {

//                if(mid>2&&mid<3)

//                    printf("x+1=%d y=%d dis=%.3lf\n",x+1,y,dis[x+1][y]);

                return ;

            }

            if(!vis[x+][y])

                vis[x+][y]=,q.push(make_pair(x+,y));

        }

        if(y<m&&dis[x][y+]<dis[x][y]+w[x][y][])

        {

            dis[x][y+]=dis[x][y]+w[x][y][];

//            printf("  w[%d][%d][2]=%.3lf\n",x,y,w[x][y][4]);

//            fa[x][y+1][0]=x; fa[x][y+1][1]=y;

            cnt[x][y+]=cnt[x][y]+;

            if(cnt[x][y+]==tot)

            {

//                if(mid>2&&mid<3)

//                    printf("x=%d y+1=%d dis=%.3lf\n",x,y+1,dis[x][y+1]);

                return ;

            }

            if(!vis[x][y+])

                vis[x][y+]=,q.push(make_pair(x,y+));

        }

    }

    return ;

}

int main()

{

    scanf("%d%d",&n,&m); tot=(n+)*(m+);//+1!!!

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

        for(int j=,d;j<=m;j++)

        {

            scanf("%d",&d); r+=d;

            fl[i][j]=fl[i][j-]+d;

//            fu[i][j]=fu[i-1][j]+d;

        }

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

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

            scanf("%d",&eh[i][j]);

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

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

            scanf("%d",&el[i][j]);

    while(r-l>eps)

    {

        mid=(l+r)/;

        if(spfa()) ans=mid,l=mid+eps;

        else r=mid-eps;

    }

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

    return ;

}

巴特西

bzoj 3232 圈地游戏——0/1分数规划(或网络流)

最新文章

热门文章