hdu 3657 Game 题解【网络流】【最小点权覆盖集】

点击量：200

最小点权覆盖集的题做起来还是挺有意思的。

目录

Problem Description

onmylove has invented a game on $ n\times m grids. There is one positive integer on each grid. Now you can take the numbers from the grids to make your final score as high as possible. The way to get score is like the following:

• At the beginning, the score is $ 0$;

• If you take a number which equals to $ x$, the score increase $ x$;

• If there appears two neighboring empty grids after you taken the number, then the score should be decreased by $ 2(x\&y)$. Here $ x$ and $ y$ are the values used to existed on these two grids. Please pay attention that “neighboring grids” means there exists and only exists one common border between these two grids.

Since onmylove thinks this problem is too easy, he adds one more rule:

• Before you start the game, you are given some positions and the numbers on these positions must be taken away.

Can you help onmylove to calculate: what’s the highest score onmylove can get in the game?

Input

Multiple input cases. For each case, there are three integers $ n, m, k$ in a line.

$ n$ and $ m$ describing the size of the grids is $ n\times m$. $ k$ means there are $ k$ positions of which you must take their numbers.

Then following $ n$ lines, each contains $ m$ numbers, representing the numbers on the $latedx n\times m$ grids.Then $ k$ lines follow. Each line contains two integers, representing the row and column of one position and you must take the number on this position.

Also, the rows and columns are counted start from $ 1$.

Limits: $ 1\le n, m\le 50, 0\le k\le n \times m$, the integer in every gird is not more than $ 1000$.

Output

For each test case, output the highest score on one line.

Sample Input

2 2 1
2 2
2 2
1 1
2 2 1
2 7
4 1
1 1

Sample Output

4
9

Hint

As to the second case in Sample Input, onmylove gan get the highest score when calulating like this:
$$ 2+7+4-2\times (2\&4) -2\times (2\&7)=13-2\times 0-2\times 2=9$$

Author
onmylove

Source
2010 Asia Regional Chengdu Site —— Online Contest

题意：

给出一个$ n\times m$的矩阵。每个格子上有一个数，如果取走一个格子上的数，会得到大小为这个数的得分。

当两个相邻格子中的数同时被取走时，需要扣掉$ 2\times(x\&y)$的分数，其中$ x,y$分别代表这两个格子上的数。

求最大得分。

题解：

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

方格取数问题问题是利用最大点权独立集来做的。答案是最小割的代价，割掉一条边表示放弃这个点，即不取它。连接二分图的两个部时，边权为正无穷，表示最小割（代价）不可能出现在点与点之间。

考虑到这个题，方格与方格之间出现了代价依赖，当取相邻方格时需要付出$ 2\times (x\&y)$的代价。

我们继续探讨在独立集/覆盖集中二分图上边的意义。

与源点或汇点相连的边如果被割了，说明这个点在最小点权覆盖集中，不取它对整个题的损失最小。

两个部分之间的边均为正无穷；我们把两个题的要求进行一个转换，对于方格取数问题，两个相邻格子不能同时被取，也就意味着取了相邻格子的代价为正无穷，而二分图中，仅有两个部分之间的边容量为正无穷。

此时把本题也建到二分图上，不过两部分之间边的容量从$ +\infty$变成了$ 2\times(x\&y)$。此时发现，当最小割出现在源点与汇点相连的边时，与原来意义一样，并没有产生不合法的情况；当最小割出现在二分图中间时，表明这两个点同时被取了，因为这条边被割了，所以产生了$ 2\times(x\&y)$的代价，这正是我们想要的。

此外，这个题还要求一些格子必须取，那么由于它是割不掉的，因此把它到源点/汇点的边容量设为$ +\infty$就可以了。（本来准备跑上下界的，发现这时意义好像有些问题）

于是像原来一样建图，相邻格子连边权值要改为$ 2\times(x\&y)$。

跑最小割，用所有点的权值和减去最小割就可以了。

tips：

注意在建二分图时不要建成双向有流了，这样可能会有些小问题。只需要从源点方向向汇点方向连边就可以了。

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[30000];
int head[2505],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[2505],q[2505];
bool bfs()
{
    int l=0,r=0;
    memset(d,0,sizeof(d));
    d[2501]=1;
    q[++r]=2501;
    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==2501)
        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(flow,e[i].v));
            if(!tmp)
                d[e[i].n]=0;
            e[i].v-=tmp;
            e[i^1].v+=tmp;
            flow-=tmp;
        }
    return in-flow;
}
int a[55][55];
bool lkd[55][55];
int main()
{
    int n,m,k,u,v;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        memset(head,-1,sizeof(head));
        memset(lkd,0,sizeof(lkd));
        ecnt=-1;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                scanf("%d",&a[i][j]);
        for(int i=1;i<=k;++i)
        {
            scanf("%d%d",&u,&v);
            lkd[u][v]=1;
        }
        int sum=0;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                sum+=a[i][j];
                if((i+j)&1)//注意区分连边，并只连一个方向
                {
                    add((i-1)*m+j,2501,lkd[i][j]?0x3fffffff:a[i][j]);
                    if(i<n)
                        add(i*m+j,(i-1)*m+j,2*(a[i][j]&a[i+1][j]));
                    if(j<m)
                        add((i-1)*m+j+1,(i-1)*m+j,2*(a[i][j]&a[i][j+1]));
                }
                else
                {        
                    add(0,(i-1)*m+j,lkd[i][j]?0x3fffffff:a[i][j]);
                    if(i<n)
                        add((i-1)*m+j,i*m+j,2*(a[i][j]&a[i+1][j]));
                    if(j<m)
                        add((i-1)*m+j,(i-1)*m+j+1,2*(a[i][j]&a[i][j+1]));
                }
            }
        int ans=0;
        while(bfs())
        {
            int tmp;
            do
            {
                tmp=dinic(0,0x3fffffff);
                ans+=tmp;
            }while(tmp);
        }
        printf("%d\n",sum-ans);
    }
    return 0;

}