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

作者: wjyyy 分类: 最小割,最小点权覆盖集,网络流,补集转换,解题报告 发布时间: 2019-01-20 11:46

点击量:95

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

题目描述

在一个有 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;
}

3
说点什么

avatar
3 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 题解 […]

trackback

[…] 之前的方格取数问题,和这个题有一定的类似点,方格取数问题是要求相邻点不能同时被取,而这里是可以取的,但是要付出一定的代价。 […]

trackback

[…] 【最小点权覆盖集】 […]

/* */