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

## 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


hanshuai

11

22
33
44
……

## 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 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];
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;
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;
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;
if((i^j)&1)
else
{
for(int k=0;k<=3;++k)
{
int x=i+X[k],y=j+Y[k];
if(x&&x<=n&&y&&y<=m)
}
}
}
for(int i=1;i<=n;++i)//s
for(int j=1;j<=m;++j)
{
scanf("%d",&u);
ans+=u;
if((i^j)&1)
{
for(int k=0;k<=3;++k)
{
int x=i+X[k],y=j+Y[k];
if(x&&x<=n&&y&&y<=m)
}
}
else
}
while(bfs())
{
int tmp=dinic(0,inf);
while(tmp)
{
ans-=tmp;
tmp=dinic(0,inf);
}
}
printf("Case %d: %d\n",t,ans);
}
return 0;
}


### 3 说点什么

0 Followers

Most reacted comment
0 Comment authors
Recent comment authors
Subscribe

[…] 详见题解 […]