题解 P1935 【[国家集训队]圈地计划】

· · 题解

好像下面的题解都是双向边
我是虚拟点做的,这样感觉也挺好理解的
思路其实都差不多,实现上略微有点差别
首先我们先看P1361 小M的作物
参考那道题的题解,可以抽象出这么一个模型
具体的解释可以参考那道题题解
然后我们回到这道题,这道题和那道题的不同之处就在于那道题两个元素在同一个集合就会有附加权值,而这道题是两个元素不在同一个集合才会有负价权值,现在就看如何转换
我用了一种十分傻瓜的方式
首先我们考虑黑白染色

我们发现白色位置的附加权值取决于四个相邻黑色位置的选择,黑色亦然
这里不用去交换源汇点 直接把其中一种颜色的A和B权值交换就行了
这样两个位置本来要选择不一样才会有附加权值
现在变成了两个位置集合相同才会有附加权值
于是这道题被完美的转化成了P1361
和那道题做法一模一样
建虚拟点,跑dinic,得答案 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 252645135
#define MAXN 1001
using namespace std;
struct side{int from,to,next,w;}edge[MAXN*MAXN];
int cur[MAXN*MAXN],head[MAXN*MAXN],depth[MAXN*MAXN],N,M,n,s,t,len=-1;
int A[MAXN][MAXN],B[MAXN][MAXN],C[MAXN][MAXN];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0},sum;
void __add_edge(int x,int y,int d){edge[++len]=(side){x,y,head[x],d};head[x]=len;}
void add_edge(int x,int y,int d)
{
    __add_edge(x,y,d);
    __add_edge(y,x,0);
}
int bfs()
{
    queue<int>q;
    for(int i=0;i<=n;i++)depth[i]=0,cur[i]=head[i];
    q.push(s);depth[s]=1;
    while(q.size())
    {
        int now=q.front();q.pop();
        for(int k=head[now];k!=-1;k=edge[k].next)
            if(edge[k].w>0&&depth[edge[k].to]==0)
                depth[edge[k].to]=depth[now]+1,
                q.push(edge[k].to);
    } 
    return depth[t]!=0;
}
int dfs(int now,int flow)
{
    if(now==t)return flow;
    for(int&k=cur[now];k!=-1;k=edge[k].next)
        if(edge[k].w>0&&depth[edge[k].to]==depth[now]+1)
        {
            int minflow=dfs(edge[k].to,min(flow,edge[k].w));
            if(minflow>0)
            {
                edge[k].w-=minflow;
                edge[k^1].w+=minflow;
                return minflow;
            }

        }
    return 0;
}
int dinic(int ans=0)
{
    while(bfs())
        while(int flow=dfs(s,INF))ans+=flow;
    return ans;
}
int point(int x,int y)
{
    return (x-1)*M+y;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>N>>M;
    n=N*M;
    s=++n;
    t=++n;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            cin>>A[i][j],sum+=A[i][j];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            cin>>B[i][j],sum+=B[i][j];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            cin>>C[i][j];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            if((i+j)%2==1)swap(A[i][j],B[i][j]); //翻转 
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            add_edge(s,point(i,j),A[i][j]);
            add_edge(point(i,j),t,B[i][j]);
        }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            for(int k=0;k<4;k++)
            {
                int nx=i+dx[k],ny=j+dy[k];
                if(0<nx&&nx<=N&&0<ny&&ny<=M)
                {
                    int x=++n;
                    int y=++n;
                    sum+=2*C[i][j];
                    add_edge(s,x,C[i][j]);
                    add_edge(x,point(i,j),INF);
                    add_edge(x,point(nx,ny),INF);
                    add_edge(y,t,C[i][j]);
                    add_edge(point(i,j),y,INF);
                    add_edge(point(nx,ny),y,INF);
                }
            }
        }
    cout<<sum-dinic();
}

希望大家有所收获