P2774 方格取数问题 |网络流最大权独立集

题目描述

有一个 \(m\) 行 \(n\) 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

输入格式

第一行是两个用空格隔开的整数，分别代表方格图的行数 \(m\) 和列数 \(n\)。

第 \(2\) 到第 \((m + 1)\) 行，每行 \(n\) 个整数，第 \((i + 1)\) 行的第 \(j\) 个整数代表方格图第 \(i\) 行第 \(j\) 列的的方格中的数字 \(a_{i, j}\)。

输出格式

输出一行一个整数，代表和最大是多少。

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e4+10,M=3e5+10,inf=1<<29;
int n,m,s,t,maxflow;
int nxt[M],head[N],go[M],edge[M],tot=1;
inline void add(int u,int v,int o){
	nxt[++tot]=head[u];head[u]=tot;go[tot]=v;edge[tot]=o;
	nxt[++tot]=head[v];head[v]=tot;go[tot]=u;edge[tot]=0;	
}
int d[N];
inline bool bfs(){
    queue<int>q; q.push(s);
    memset(d,0,sizeof(d)); d[s]=1;
    while(q.size()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v=go[i];
            if(edge[i]&&!d[v]){
                d[v]=d[u]+1;
                if(v==t)return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
int dinic(int u,int flow){
    if(u==t)return flow;
    int rest=flow,k;
    for(int i=head[u];i;i=nxt[i]){
        int v=go[i];
        if(edge[i]&&d[v]==d[u]+1){
            k=dinic(v,min(edge[i],rest));
            if(!k)d[v]=-1;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
inline int P(int x,int y){
    return (x-1)*m+y;
}
int a[105][105];
signed main(){
    cin>>n>>m; int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]),ans+=a[i][j];
    t=n*m+2; s=n*m+3;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){  
        if((i+j)&1)add(s,P(i,j),a[i][j]);
        else add(P(i,j),t,a[i][j]);
        if((i+j)&1){
            if(i>1)add(P(i,j),P(i-1,j),inf);
            if(j>1)add(P(i,j),P(i,j-1),inf);
            if(i<n)add(P(i,j),P(i+1,j),inf);
            if(j<m)add(P(i,j),P(i,j+1),inf);
        }
    }
    int flow=0;
    while(bfs())
    while(flow=dinic(s,inf))maxflow+=flow;
    cout<<ans-maxflow<<endl;
}

P2774 方格取数问题 |网络流最大权独立集

原文：https://www.cnblogs.com/naruto-mzx/p/12922536.html