洛谷 P2774 方格取数问题 题解【网络流】【最小点权覆盖集】

点击量：325

学到了方格图上的一种建模方向。

目录

题目描述

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

输入输出格式

输入格式：

第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。

输出格式：

程序运行结束时，将取数的最大总和输出

输入输出样例

输入样例#1：

3 3
1 2 3
3 2 3
2 3 1 

输出样例#1：

11

说明

m,n<=100

题解：

首先建立二分图。在方格图中，如果表示两相邻只取一个，可以转化为二分图问题。如POJ 2446 Chessboard。

假设一个点的坐标是$ (x,y)$，则当$ x+y$是奇数时令其在二分图左侧，为偶数时在二分图右侧。也就是说，对于原方格图上的点，从$ (1,1)$颜色为黑开始逐一染色，对相邻的点连边。

这样构成一个二分图后，跑最大点权独立集即可。

附：最大点权独立集求法

概念等可以看论文和网上资料。

在二分图中，最大点权独立集与最小点权覆盖集互补。因此求出最小点权覆盖集，再补集转换就可以求出这题的答案。

首先证明独立集与覆盖集互补。当二分图中的一个点集是独立集时，它们中的任意两点没有连边。如果它的补集不是覆盖集，那么存在一条边，它的两边都不在覆盖集中。此时这两个点相连，与“独立集”矛盾。

同理，当二分图中的一个点集是覆盖集时，所有的边都有一个顶点在覆盖集中。如果它的补集不是独立集，那么存在一条边连接了补集中的两点，而由于所有边都存在顶点都在覆盖集中，产生矛盾。

而由于权值和是恒定的，上述两集互补，因此当其中一个最大时，另一个最小。一般根据现实情况，独立集要求最大、覆盖集要求最小才有意义（不然分别取一个点和全部点就满足最小和最大了）。

然后对于二分图，把源点连到其中一组染色相同的点，把另一组与汇点相连。原先存在的点之间用容量为$ \inf$的边相连，与源点或汇点的边容量就是原先存在点的点权。

此时求出最小割，就是最小点权覆盖集，再补集转换，用全部的值减去这个最小割就是答案了。

Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[50000];
int head[10010],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],0);
    head[to]=ecnt;
}
int d[10500],q[10500];
//源点0，汇点10001
bool bfs()
{
    int l=0,r=0;
    memset(d,0,sizeof(d));
    d[10001]=1;
    q[++r]=10001;
    while(l<r)
    {
        int x=q[++l];
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i^1].v&&!d[e[i].n])
            {
                d[e[i].n]=d[x]+1;
                q[++r]=e[i].n;
            }
    }
    return d[0]>0;
}
int dinic(int x,int in)
{
    if(x==10001)
        return in;
    int flow=in;
    for(int i=head[x];flow&&~i;i=e[i].nxt)
        if(e[i].v&&d[e[i].n]==d[x]-1)
        {
            int tmp=dinic(e[i].n,Min(e[i].v,flow));
            if(!tmp)
                d[e[i].n]=0;
            e[i].v-=tmp;
            e[i^1].v+=tmp;
            flow-=tmp;
        }
    return in-flow;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,u,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&u);
            ans+=u;
            if((i+j)&1)
            {
                add((i-1)*m+j,10001,u);
                if(i<n)
                    add(i*m+j,(i-1)*m+j,0x3fffffff);
                if(j<m)
                    add((i-1)*m+j+1,(i-1)*m+j,0x3fffffff);
            }
            else
            {
                add(0,(i-1)*m+j,u);
                if(i<n)
                    add((i-1)*m+j,i*m+j,0x3fffffff);
                if(j<m)
                    add((i-1)*m+j,(i-1)*m+j+1,0x3fffffff);
            }
        }
    while(bfs())
    {
        int tmp;
        do
        {
            tmp=dinic(0,0x3fffffff);
            ans-=tmp;
        }while(tmp);
    }
    printf("%d\n",ans);
    return 0;
}