方格取数问题

复习一下网络流。。。

传送门

题目描述

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

做法：

这题的二分图模型十分套路，是一道二分图带权最大独立集问题，有一个结论：二分图最大独立集=所有的点权-最小点覆盖数（用最少的点覆盖所有边）。

解释一下：因为所有的边已经被最小点覆盖点集中的点覆盖了，那么删掉这些点就是删掉所有边，剩下的点都是不联通且最大的。

而根据König定理，最小点覆盖=最大匹配。所以我们只要求最大匹配就好了。

（吐槽一下：这个定理网上证明并不多，而且许多证明都是用“显然”混过去了关键点，其他题解也没有说为什么是总点权-最小割，这里推荐Matrix67的证明）

这样我们就把横纵坐标奇偶性相同的点放在二分图的一侧，对相邻的点连一条容量为无限的边，二分图两侧的点分别向源点和汇点连一条容量为点权的边，之后跑一边最小割即可。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
    int x,y,next,z;
}w[2000001];
int tail,m,deep[110][110],head[110][110],a[110][110];
int heap,n,team[10010][2],cnt,tim,sum,ans,o[110][110];
int dx[5]={0,-1,0,1,0},dy[5]={0,0,-1,0,1};
inline void add(int x1,int y1,int x2,int y2,int z){
    w[cnt].next=head[x1][y1];
    w[cnt].x=x2; w[cnt].y=y2;
    w[cnt].z=z; head[x1][y1]=cnt; cnt++;
}
inline bool bfs(){
    heap=tail=1; tim++; o[0][0]=tim;
    team[heap][0]=team[heap][1]=0;
    deep[0][0]=1;
    while (heap<=tail){
        int x=team[heap][0],y=team[heap][1];
        for (int i=head[x][y]; i!=-1; i=w[i].next){
            if (w[i].z&&o[w[i].x][w[i].y]!=tim){
                tail++; o[w[i].x][w[i].y]=tim;
                deep[w[i].x][w[i].y]=deep[x][y]+1;
                team[tail][0]=w[i].x; team[tail][1]=w[i].y;
            }
        }
        heap++;
    }
    return (o[n+1][m+1]==tim);
}
int dfs(int x,int y,int l){
    if ((!l)||(x==n+1&&y==m+1)) return l;
    int used=0,minn,z;
    for (int i=head[x][y]; i!=-1; i=w[i].next){
        if (deep[w[i].x][w[i].y]==deep[x][y]+1&&w[i].z){
            minn=min(l-used,w[i].z);
            z=dfs(w[i].x,w[i].y,minn);
            if (z){
                w[i].z-=z; w[i^1].z+=z;
                used+=z; if (used==l) break;
            }
        }
    }
    if (!used) deep[x][y]=0;
    return used;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++){
            scanf("%d",&a[i][j]); sum+=a[i][j];
        }
    memset(head,-1,sizeof(head));
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++){
            if (i%2==j%2){
                add(0,0,i,j,a[i][j]);
                add(i,j,0,0,0);
                for (int k=1; k<=4; k++){
                    if (i+dx[k]<=0||i+dx[k]>n) continue;
                    if (j+dy[k]<=0||j+dy[k]>m) continue;
                    add(i,j,i+dx[k],j+dy[k],1e9);
                    add(i+dx[k],j+dy[k],i,j,0);
                }
            }
            else{
                add(i,j,n+1,m+1,a[i][j]);
                add(n+1,m+1,i,j,0);
            }
        }
    while (bfs()) ans+=dfs(0,0,1e9);
    printf("%d\n",sum-ans);
    return 0;
}