Game

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

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 × (2&4) － 2 × (2&7) = 13 － 2 × 0 － 2 × 2 = 9.
 

题目描写叙述：n*m的矩阵，每一个位置都有一个正数，一開始你的分数是0。当你取走一个数字时，你的分数添加那个分数。假设你取完数字后。新出现了2个相邻的都是空的格子，那么你的分数降低2 * ( x & y)，x，y是那两个格子的原始数值。

同一时候有一些附加条件，有一些格子的数字是必须拿走的。

解题：与方格取数几乎相同。注要多了两个不同的条件。

1.取相邻的格子则要降低2*(x&y) 建图时。相邻两个格子之间建边容量为2*(x&y)  2.有K个格子是必须取的，则与必须取的点相连的点S或T的边的容量为INF。这样在求最小割时就不会被割了。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define captype int

const int MAXN = 100010;   //点的总数
const int MAXM = 400010;    //边的总数
const int INF = 1<<30;
struct EDG{
    int to,next;
    captype cap,flow;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];  //每种距离(或可觉得是高度)点的个数
int dis[MAXN];  //每一个点到终点eNode 的最短距离
int cur[MAXN];  //cur[u] 表示从u点出发可流经 cur[u] 号边
int pre[MAXN];

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
//有向边 三个參数。无向边4个參数
void addEdg(int u,int v,captype c,captype rc=0){
    edg[eid].to=v; edg[eid].next=head[u];
    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v];
    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
captype maxFlow_sap(int sNode,int eNode, int n){//n是包含源点和汇点的总点个数。这个一定要注意
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    pre[sNode] = -1;
    gap[0]=n;
    captype ans=0;  //最大流
    int u=sNode;
    while(dis[sNode]<n){   //推断从sNode点有没有流向下一个相邻的点
        if(u==eNode){   //找到一条可增流的路
            captype Min=INF ;
            int inser;
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to])    //从这条可增流的路找到最多可增的流量Min
            if(Min>edg[i].cap-edg[i].flow){
                Min=edg[i].cap-edg[i].flow;
                inser=i;
            }
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){
                edg[i].flow+=Min;
                edg[i^1].flow-=Min;  //可回流的边的流量
            }
            ans+=Min;
            u=edg[inser^1].to;
            continue;
        }
        bool flag = false;  //推断是否能从u点出发可往相邻点流
        int v;
        for(int i=cur[u]; i!=-1; i=edg[i].next){
            v=edg[i].to;
            if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){
                flag=true;
                cur[u]=pre[v]=i;
                break;
            }
        }
        if(flag){
            u=v;
            continue;
        }
        //假设上面没有找到一个可流的相邻点。则改变出发点u的距离（也可觉得是高度）为相邻可流点的最小距离+1
        int Mind= n;
        for(int i=head[u]; i!=-1; i=edg[i].next)
        if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){
            Mind=dis[edg[i].to];
            cur[u]=i;
        }
        gap[dis[u]]--;
        if(gap[dis[u]]==0) return ans;  //当dis[u]这样的距离的点没有了，也就不可能从源点出发找到一条增广流路径
                                        //由于汇点到当前点的距离仅仅有一种。那么从源点到汇点必定经过当前点。然而当前点又没能找到可流向的点，那么必定断流
        dis[u]=Mind+1;//假设找到一个可流的相邻点。则距离为相邻点距离+1，假设找不到，则为n+1
        gap[dis[u]]++;
        if(u!=sNode) u=edg[pre[u]^1].to;  //退一条边
    }
    return ans;
}
int main()
{
    int n,m,k,cost[55][55],flag[55][55];
    int dir[4][2]={0,1,0,-1,1,0,-1,0};
    while(scanf("%d%d%d",&n,&m,&k)>0)
    {
        init();
        int s=n*m,t=n*m+1 , ans=0;
        for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            scanf("%d",&cost[i][j]);
           ans+=cost[i][j];
        }
        int x,y;
        memset(flag,0,sizeof(flag));
        while(k--)
        {
            scanf("%d%d",&x,&y); x--; y--;
            flag[x][y]=1;
        }
        for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        if((i+j)&1)
        {
            addEdg(s , i*m+j , flag[i][j]==0?cost[i][j]:INF);
            for(int e=0; e<4; e++)
             {
                 x=i+dir[e][0];
                 y=j+dir[e][1];
                 if(x>=0&&x<n&&y>=0&&y<m)
                  addEdg(i*m+j, x*m+y,2*(cost[i][j]&cost[x][y]));
             }
        }
        else
            addEdg(i*m+j,t,flag[i][j]==0?cost[i][j]:INF);
            
        ans-=maxFlow_sap(s , t, t+1);
        printf("%d\n",ans);
    }
}