2014
11-30

# Game

onmylove has invented a game on n × 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 exits and only exits 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?

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 ×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 n×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 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.

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 ×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 n×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 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.

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

4
9

HintAs to the second case in Sample Input, onmylove gan get the highest score when calulating like this:
2 + 7 + 4 － 2 × (2&4) － 2 × (2&7) = 13 － 2 × 0 － 2 × 2 = 9. 

http://acm.hdu.edu.cn/showproblem.php?pid=3657

#include<iostream>
using namespace std;
#define N 2550
#define M 2000000
#define inf 0x7fffffff
struct Graph{
struct node{
int v,next,flow;
node(){};
node(int a,int b,int c):next(a),v(b),flow(c){};
}E[M];
int pre[N];
int cur[N];
int dis[N];
int NV,NE;
int gap[N];
void init(int n){
NE=0;
NV=n;
}
void insert(int u,int v,int w){
}
int SAP(int s,int t){
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
for(int i=0;i<NV;i++)
int u=pre[s]=s;
int maxflow=0,aug=INT_MAX;
gap[0]=NV;
while(dis[s]<NV){
loop:   for(int &i=cur[u];i!=-1;i=E[i].next){
int v=E[i].v;
if(E[i].flow&&dis[u]==dis[v]+1){
if(aug>E[i].flow)
aug=E[i].flow;
pre[v]=u;
u=v;
if(v==t){
maxflow+=aug;
for(u=pre[u];v!=s;v=u,u=pre[u]){
E[cur[u]].flow-=aug;
E[cur[u]^1].flow+=aug;
}
aug=INT_MAX;
}
goto loop;
}
}
int mindis=NV;
int v=E[i].v;
if(E[i].flow&&mindis>dis[v]){
cur[u]=i;
mindis=dis[v];
}
}
if(--gap[dis[u]]==0)
break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return maxflow;
}
}G;
int map[55][55];
int main(void){
int n,m,k;
while(~scanf("%d%d%d",&n,&m,&k)){
int beg=n*m+1,end=beg+1;
G.init(end);
int s=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&map[i][j]);
s+=map[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int u=(i-1)*m+j;
if((i+j)%2){
G.insert(beg,u,map[i][j]);
if(i>1) G.insert(u,u-m,2*(map[i][j]&map[i-1][j]));
if(j>1) G.insert(u,u-1,2*(map[i][j]&map[i][j-1]));
if(i<n) G.insert(u,u+m,2*(map[i][j]&map[i+1][j]));
if(j<m) G.insert(u,u+1,2*(map[i][j]&map[i][j+1]));
}
else
G.insert(u,end,map[i][j]);
}
while(k--){
int x,y;
scanf("%d%d",&x,&y);
int u=(x-1)*m+y;
if((x+y)%2){
if(G.E[i].v==u){
G.E[i].flow=inf;
break;
}
}
else{
if(G.E[i].v==end){
G.E[i].flow=inf;
break;
}
}
}
printf("%d\n",s-G.SAP(beg,end));
}
}


1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法