luogu 4142

费用流好题

本题的建图很有意思

正常我们看到棋盘问题应该先对整个棋盘黑白染色构成一个二分图，然后再考虑建图的问题

但是本题题目中已经明确区分了不同的斜线，问题在于怎么保证一个"L"形

因此我们进一步分析：显然柱子应该放在有代价的位置，我们应该由这样的位置向上下左右连边，保证有两个就行

但是这样建图是有问题的，因为首先，难以保证选了两个位置，其次，上下/左右这种选两个的方式也是不合法的！

因此我们考虑进一步拆解这个图：我们把这个图分成三部分（请自动忽略坏点），一部分是产生代价的地方，一部分是行列号均为偶数的部分，一部分是行列号均为奇数的部分

然后我们这样建图：源点->二级源点->行列号均为偶数的部分->产生代价的部分->行列号均为奇数的部分->汇点

其中二级源点是为了限制流量不得大于$m$的

这样连边之后，就很好的保证了必须选两个且排除了选上下两个/左右两个的情况

中间的点需要拆点，拆出来两个点流量为1，费用给出

注意跑的是最大费用流，跑出来以后还要用总费用减去这个最大费用，同时我们并不需要让流量最大，因此如果费用为负直接跳出

贴代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

using namespace std;

const int inf=0x3f3f3f3f;

struct Edge

{

    int nxt;

    int to;

    int val;

    int pri;

}edge[5000005];

int lim[10005];

int to[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

bool vis[55][55];

bool used[10005];

int dis[10005];

int w[55][55];

int val[10005];

int head[10005];

int pre[10005],f[10005];

int tot=0,cnt=1;

int n,m,k;

int ans=0;

int st,ed,eed;

int idx(int x,int y)

{

    return (x-1)*n+y;

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool check(int x,int y)

{

    return x>0&&x<=n&&y>0&&y<=n&&!vis[x][y];

}

void add(int l,int r,int z,int v)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=z;

    edge[cnt].pri=v;

    head[l]=cnt++;

}

void dadd(int l,int r,int z,int v)

{

    add(l,r,z,v),add(r,l,0,-v);

}

bool spfa()

{

    memset(dis,-0x3f,sizeof(dis));

    memset(pre,-1,sizeof(pre));

    memset(f,0,sizeof(f));

    dis[tot+1]=0;

    used[tot+1]=1;

    lim[tot+1]=inf;

    queue <int> M;

    M.push(tot+1);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&dis[to]<dis[u]+edge[i].pri)

            {

                dis[to]=dis[u]+edge[i].pri;

                lim[to]=min(lim[u],edge[i].val);

                f[to]=u,pre[to]=i;

                if(!used[to])M.push(to),used[to]=1;

            }

        }

        used[u]=0;

    }

    return dis[tot+3]>0&&pre[tot+3]!=-1;

}

int EK()

{

    int maxf=0,maxv=0;

    while(spfa())

    {

        maxf+=lim[tot+3],maxv+=lim[tot+3]*dis[tot+3];

        int temp=tot+3;

        while(temp!=tot+1)

        {

            edge[pre[temp]].val-=lim[tot+3];

            edge[ide(pre[temp])].val+=lim[tot+3];

            temp=f[temp];

        }

    }

    return maxv;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    tot=n*n*2;

    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&w[i][j]),ans+=w[i][j];

    dadd(tot+1,tot+2,m,0);

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

    {

        int x,y;

        scanf("%d%d",&x,&y);

        vis[x][y]=1;

    }

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

    {

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

        {

            if(vis[i][j])continue;

            dadd((idx(i,j)<<1)-1,idx(i,j)<<1,1,w[i][j]);

            if((i&1)&&(j&1))dadd(idx(i,j)<<1,tot+3,1,0);

            else if(!(i&1)&&!(j&1))

            {

                dadd(tot+2,(idx(i,j)<<1)-1,1,0);

                for(int t=0;t<4;t++)

                {

                    int toi=i+to[t][0],toj=j+to[t][1];

                    if(!check(toi,toj))continue;

                    dadd(idx(i,j)<<1,(idx(toi,toj)<<1)-1,1,0);

                }

            }else

            {

                for(int t=0;t<4;t++)

                {

                    int toi=i+to[t][0],toj=j+to[t][1];

                    if(!check(toi,toj)||!(toi&1)||!(toj&1))continue;

                    dadd(idx(i,j)<<1,(idx(toi,toj)<<1)-1,1,0);

                }

            }

        }

    }

    printf("%d\n",ans-EK());

    return 0;

}

巴特西

luogu 4142

最新文章

热门文章