洛谷 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;
}