P2774 方格取数问题(网络流24题-最小割建图)

题目链接

https://www.luogu.org/problem/P2774

题目大意

在一个有 m*n 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。

解题思路

最小割建图
我们将棋盘想象成国际象棋的棋盘,就是说从一个黑格子不能走向相邻的白格子,
这是一个最基本的非法路径,对于整张图来说就是要避免出现图中的这种情况,只要整张图中都没有这样的通路,也就没有从黑点到相邻白点的非法状态了。
所以我们将所有的黑点与其四周的白点连边(b)边权inf,
将源点与所有的黑点连接,边权为黑点的权值(a),
将所有的白点与汇点连接,边权为白点的权值(c),
这样建图的意义在于当跑最小割的时候,比如割断了(a)边的时候代表不取这个黑点,割断了(c)边的时候代表不取这个白点,但一定不会隔断(b),这样就可以求得使图合法所需要的最小代价(不取的点权和),用总点权和剪掉最小割的就是合法的最大点权和了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+100;
const int inf=0x3f3f3f3f;
int a[maxn],dp[maxn];
int n,m;
int S,T;
struct node {
    int v,nxt,w;
} edge[maxn];
int head[maxn*2],cur[maxn*2],dep[maxn*2];
int tot=0,maxflow=0;
void add(int u,int v,int w) {
    edge[tot]= {v,head[u],w};
    head[u]=tot++;
    edge[tot]= {u,head[v],0};
    head[v]=tot++;
}
bool bfs(int s,int t) {
    memset(dep,-1,sizeof(dep));
    queue<int>q;
    dep[s]=0;
    q.push(s);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=head[now]; i!=-1; i=edge[i].nxt) {
            if(dep[edge[i].v]==-1&&edge[i].w>0) {
                dep[edge[i].v]=dep[now]+1;
                q.push(edge[i].v);
                if(edge[i].v==T)
                    return 1;
            }
        }
    }
    return false;
}
int dfs(int now,int t,int limit) {
    if(!limit||now==t) {
        return limit;
    }
    int flow=0,f=0;
    for(int i=cur[now]; i!=-1; i=edge[i].nxt) {
        cur[now]=i;
        int v=edge[i].v;
        if(dep[v]==dep[now]+1&&edge[i].w>0&&
           (f=dfs(v,t,min(limit,edge[i].w)))) {
            flow+=f;
            limit-=f;
            edge[i].w-=f;
            edge[i^1].w+=f;
            if(!limit)
                break;
        }
    }
    if(flow==0)
        dep[now]=-1;
    return flow;
}
void dinic(int s,int t) {
    while(bfs(s,t)) {
        memcpy(cur,head,sizeof(head));
        maxflow+=dfs(s,t,inf);
    }
}
int main() {
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    S=n*m;
    T=n*m+1;
    long long d,sum=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin>>d;
            sum+=d;
            if((i+j)%2==0) {
                add(S,(i*m+j),d);
                if(i<n-1) {
                    add((i*m+j),i*m+m+j,inf);
                }
                if(j<m-1) {
                    add((i*m+j),i*m+j+1,inf);
                }
                if(i>0) {
                    add((i*m+j),i*m-m+j,inf);
                }
                if(j>0) {
                    add((i*m+j),i*m+j-1,inf);
                }
            } else {
                add((i*m+j),T,d);
            }
        }
    }
    //½¨±ß
    maxflow=0;
    dinic(S,T);
    //cout<<maxflow<<endl;
    cout<<sum-maxflow<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注