hdu 3820 Golden Eggs 题解【网络流】【最小点权独立集】

点击量：490

目录

Problem Description

There is a grid with N rows and M columns. In each cell you can choose to put a golden or silver egg in it, or just leave it empty. If you put an egg in the cell, you will get some points which depends on the color of the egg. But for every pair of adjacent eggs with the same color, you lose G points if there are golden and lose S points otherwise. Two eggs are adjacent if and only if there are in the two cells which share an edge. Try to make your points as high as possible.

Input

The first line contains an integer T indicating the number of test cases.

There are four integers N, M, G and S in the first line of each test case. Then 2*N lines follows, each line contains M integers. The j-th integer of the i-th line Aij indicates the points you will get if there is a golden egg in the cell(i,j). The j-th integer of the (i+N)-th line Bij indicates the points you will get if there is a silver egg in the cell(i,j).

Technical Specification

1. 1 <= T <= 20
2. 1 <= N,M <= 50
3. 1 <= G,S <= 10000
4. 1 <= Aij,Bij <= 10000

Output

For each test case, output the case number first and
then output the highest points in a line.

Sample Input

2
2 2 100 100
1 1
5 1
1 4
1 1
1 4 85 95
100 100 10 10
10 10 100 100

Sample Output

Case 1: 9
Case 2: 225

Author

hanshuai

题意

给出一个$ n\times m$的矩阵，每个格子$ (i,j)$有$ A_{i,j}$和$ B_{i,j}$两个权值。每个格子可以选择放金蛋、银蛋或者不放，如果放置则只能放置一个。在$ (i,j)$放置金蛋会得到$ A_{i,j}$分；放置银蛋会得到$ B_{i,j}$分；不放置则不得分。

每当相邻两个格子同时出现金蛋时，就会扣掉$ G​$分，每当相邻两个格子同时出现银蛋时，就会扣掉$ S​$分。

最大化得分，并输出。

题解

这个题的基础还是方格取数问题。不过方格取数问题是二选一——选或不选，而这个题是三选一。

同时这个题可以让你付出代价来选择相邻相同颜色的蛋，就更像hdu 3657 Game了。（在这个题中是把权值为$ \inf$的边改为相邻方格同时放置的代价了。）

而在本题中，需要注意的点有：金银至多取一个，不能同时取。相邻方格里有相同元素时要扣掉相应的分。可以存在一些不取的格子。

因此想到了和之前类似的建模方法，如果直接黑白染色，黑色在源点一边，白色在汇点一边，那么控制金银至多取一个就成了难题。

而如果让金色在源点一边，白色在汇点一边，那么无法控制相邻位置付出的代价，而且每个点都得有一颗蛋。

实际上我们把上面的两种方法结合起来就能得到正确的建模方法了。

上面需要注意的点只提到了互相限制的因素，而没有提到不互相限制的因素，而正是不互相限制的因素才能放在二分图的同一侧。

在本题中，当相邻两个格子分别放金蛋和银蛋时，它们并不互相影响，也不产生额外的代价。

我们假设已经染好色了。奇数(1,3,…)为黑色点、偶数(2,4,…)为白色点。那么二分图的两侧就分别是

1 → 1

2 → 2
3 → 3
4 → 4
……

此时同侧的点不会互相影响，只有对侧的点才会对代价造成一定影响，然后在他们之间连接容量为代价的边即可。

例如在2→3（假定2,3相邻）中这条边的容量就是$ S$。再回到最小点权覆盖集中，它计算的是失去哪些边会造成最小损失，因此当2→3这样的边成为割边时，表示用$ S$这么大的代价来换取银色的2,3同时出现。

再为了满足一个格子里最多放一颗蛋，1→1的容量为$ \inf​$，如果不添加这样的边的话，就可能导致每个格子的两颗蛋表示的边都还没有被切断，就形成了割。

然后跑二分图上的最大流，表示最小割，代表了需要承受的最小损失。最终答案就是$ \left(\sum_{i=1}^n\sum_{j=1}^mA_{i,j}+B_{i,j}\right)-maxflow$也就是所有位置所有颜色的权值和减去最大流的值。

注意拆点和多组数据。

Code：

#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
int Min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int n,v,nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge(){}
}e[50000];
int head[5500],ecnt=-1;
//无关的
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,v,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,0,head[to]);
    head[to]=ecnt;
}
int X[4]={-1,0,0,1};
int Y[4]={0,-1,1,0};
//TT=5050
int q[5500],d[5500];
bool bfs()
{
    memset(d,0,sizeof(d));
    int l=0,r=0;
    q[++r]=5050;
    d[5050]=1;
    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==5050)
        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;
            flow-=tmp;
            e[i].v-=tmp;
            e[i^1].v+=tmp;
        }
    return in-flow;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;++t)
    {
        int ans=0;
        memset(head,-1,sizeof(head));
        ecnt=-1;
        int n,m,G,S,u;
        scanf("%d%d%d%d",&n,&m,&G,&S);
        int tot=n*m;
        for(int i=1;i<=n;++i)//g
            for(int j=1;j<=m;++j)
            {
                scanf("%d",&u);
                ans+=u;
                add((i-1)*m+j,(i-1)*m+j+tot,inf);
                if((i^j)&1)
                    add((i-1)*m+j+tot,5050,u);
                else
                {
                    add(0,(i-1)*m+j,u);
                    for(int k=0;k<=3;++k)
                    {
                        int x=i+X[k],y=j+Y[k];
                        if(x&&x<=n&&y&&y<=m)
                            add((i-1)*m+j,(x-1)*m+y+tot,G);
                    }
                }
            }
        for(int i=1;i<=n;++i)//s
            for(int j=1;j<=m;++j)
            {
                scanf("%d",&u);
                ans+=u;
                if((i^j)&1)
                {
                    add(0,(i-1)*m+j,u);
                    for(int k=0;k<=3;++k)
                    {
                        int x=i+X[k],y=j+Y[k];
                        if(x&&x<=n&&y&&y<=m)
                            add((i-1)*m+j,(x-1)*m+y+tot,S);
                    }
                }
                else
                    add((i-1)*m+j+tot,5050,u);
            }
        while(bfs())
        {
            int tmp=dinic(0,inf);
            while(tmp)
            {
                ans-=tmp;
                tmp=dinic(0,inf);
            }
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}