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

吾王美如画 · 2019-03-10 20:33:32 · 题解

唔姆

正如各位大佬所说，这题和P1646很像，但我觉得真正想通了，这题比P1646容易鸭 (我甚至有了抄我以前写的P1646题解的想法了

• 首先，和P1646一样，我们把每个点从源点连一条容量商业区的收益的边，向汇点连一条容量为工业区的边。
• 接着，我们在把相邻的点连起来时，我们发现，因为题目要求的是不相同才会有额外收益，而直接连边就不合理了
• 然后呢，我们又发现，所谓相邻的就是上下左右四个点，所以可以像棋盘那样以行列奇偶性染个色，把一种颜色给倒过来，也就是之前连汇，现在就连源，之前连源，现在就连汇
• 记得是双向边哦（虽然我就直接link两次）
• 最后直接把总收益-最小割就OK了

（一点都没P1646愉♂悦）

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 100050
#define MAXM 150005
using namespace std;
int head[MAXN],next[MAXM*2],to[MAXM*2],w[MAXM*2];
int n,m,S,T;
int cnt=-1;
int deep[MAXN];
void link(int a,int b,int c){
     cnt++;
     w[cnt]=c;
     next[cnt]=head[a];
     to[cnt]=b;
     head[a]=cnt;
     cnt++;
     w[cnt]=0;
     next[cnt]=head[b];
     to[cnt]=a;
     head[b]=cnt;
}
bool bfs(){
     memset(deep,0,sizeof(deep));
     queue<int> q;
     while(!q.empty())q.pop();
     q.push(S);
     deep[S]=1;
     while(!q.empty()){
                       int now=q.front();
                       q.pop();
                       for(int i=head[now];i!=-1;i=next[i]){
                               if (w[i]&&!deep[to[i]]){
                                                       deep[to[i]]=deep[now]+1;
                                                       q.push(to[i]);
                               }
                       }
     }
     if (deep[T])return 1;else return 0;
}
int dinic(int now,int last){
    if (now==T||!last)return last;
    int ret=0;
    for(int i=head[now];i!=-1;i=next[i]){
            if(deep[to[i]]-1==deep[now]&&w[i]){
                                               int zgl=dinic(to[i],min(w[i],last-ret));
                                               if (zgl){
                                                        w[i]-=zgl;
                                                        w[i^1]+=zgl;     
                                                        ret+=zgl;
                                               }
            }
    }
    if (!ret)deep[now]=-1;
    return ret;
}
int num(int a,int b){
    return m*(a-1)+b;
}
int c[200][200];
int main(){
    cin>>n>>m;
    S=0;T=MAXN-1;
    int a;
    memset(head,-1,sizeof(head));
    long long sum=0;
    for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                    scanf("%d",&a);
                    if ((i+j)&1)link(S,num(i,j),a);
                    else link(num(i,j),T,a);
                    sum+=a;
            }
    }
    for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                    scanf("%d",&a);
                    if ((i+j)&1)link(num(i,j),T,a);
                    else link(S,num(i,j),a);
                    sum+=a;
            }
    }
    for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                    scanf("%d",&c[i][j]);
    int tx[]={0,-1,0,1},ty[]={1,0,-1,0};
    for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                    for(int k=0;k<4;k++){
                            int xx=i+tx[k],yy=j+ty[k];
                            if (xx<=0||xx>n)continue;
                            if (yy<=0||yy>m)continue;
                            link(num(i,j),num(xx,yy),c[i][j]+c[xx][yy]);
                            sum+=c[i][j];
                    }
            }
    }
    long long ans=0;
    while(bfs())
                 ans+=dinic(S,9999999);
    cout<<sum-ans;
    return 0;
}