洛谷 P1935 [国家集训队]圈地计划 网络流 最小割 Dinic+当前弧优化 不在一类额外奖励转化为在一类额外奖励

题目链接：

https://www.luogu.com.cn/problem/P1935

思路来源博客：

https://www.luogu.com.cn/blog/sjf-a-newcomer/solution-p1935

这个博客对这类题目的解释非常到位，一定要再看

算法：1：最小割 Dinic+当前弧优化 不在一类额外奖励转化为在一类额外奖励

思路：

1：这道题和这类题目的其它题型区别在于，其它题两个元素在同一个集合就会有附加权值,而这道题是两个元素不在同一个集合才会有附加权值,现在就看如何转换

2：直接把其中一种颜色的a和b权值交换就行了，这样两个位置本来要选择不一样才会有附加权值，现在变成了两个位置集合相同才会有附加权值，于是就变成了我们熟悉的那种类型了

图解：

代码：

#include <bits/stdc++.h>
#define xuhao(i,j) ((i-1)*m+j)
#define hefa(i,di,top) (di<=i&&i<=top)
//Dinic+当前弧优化

using namespace std;
const int maxn=9e4+2,maxm=5e5+2e4+1,inf=0x7fffffff;
int n,m,s,t,tot=1,head[maxn],cur[maxn],dep[maxn],ans,sum,cnt;//用上了分层图，可以用dep判重了
int a[101][101],b[101][101],c[101][101];
const int d[4][2]=
{
    {1,0},{-1,0},{0,1},{0,-1}
};

struct edge
{
    int to,next,w;
}e[maxm];

void addedge(int x,int y,int w)
{
    e[++tot].to=y;e[tot].w=w;e[tot].next=head[x];head[x]=tot;
    e[++tot].to=x;e[tot].w=0;e[tot].next=head[y];head[y]=tot;
}

bool bfs()//bool 函数是一个小优化，判断是否能搜到汇点，如果连汇点都搜不到还dfs干什么？
{
    memset(dep,0,sizeof dep);//一定要初始化
    memcpy(cur,head,sizeof(head));
    queue<int>q;
    q.push(s);dep[s]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].next)
        {
            int y=e[i].to,w=e[i].w;
            if(w&&!dep[y])//如果有残余流量（没有的话谁也过不去）并且这个点是第一次到达
            {
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }
    }
    return dep[t];//t 的深度不为0，就是搜到了汇点
}

int dfs(int u,int flow) {
    if(u==t) return flow;
    int ans=0;
    for(int i=cur[u];i&&ans<flow;i=e[i].next) {
        cur[u]=i;
        int v=e[i].to;
        if(e[i].w&&dep[v]==dep[u]+1) {
            int x=dfs(v,min(e[i].w,flow-ans));
            if(x) e[i].w-=x,e[i^1].w+=x,ans+=x;
        }
    }
    if(ans<flow) dep[u]=-1;//说明这个点已经榨干
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    scanf("%d %d",&n,&m);
    s=0,t=n*m+1,cnt=t;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&b[i][j]),sum+=b[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&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++)
        addedge(s,xuhao(i,j),a[i][j]),addedge(xuhao(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 x=i+d[k][0],y=j+d[k][1];
        if(hefa(x,1,n)&&hefa(y,1,m))
        {
            sum+=c[i][j];
            addedge(s,++cnt,c[i][j]);
            addedge(cnt,xuhao(i,j),inf),addedge(cnt,xuhao(x,y),inf);
            sum+=c[i][j];
            addedge(++cnt,t,c[i][j]);
            addedge(xuhao(i,j),cnt,inf),addedge(xuhao(x,y),cnt,inf);
        }
    }
    while(bfs())ans+=dfs(s,inf);
    printf("%d\n",sum-ans);
    return 0;
}