方格取数(1)

/* ***********************************************Author        :哈特13Created Time  :2015/1/7 23:38:02File Name     :HDU 1565 方格取数(1).cpp************************************************ */#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <vector>#include <queue>#include <set>#include <string>#include <cmath>#include <cstdlib>#include <ctime>using namespace std;#define INF 0x3f3f3f3f#define ll long long#define N 510int n;int src;int des;int sum;int pre[N];int mpt[N][N];int map[N][N];int dir[4][2]={1,0,-1,0,0,1,0,-1};queue<int> q;bool bfs(){    while(!q.empty()) q.pop();    memset(pre,-1,sizeof(pre));    pre[src]=0;    q.push(src);    while(!q.empty())    {        int u=q.front();        q.pop();        for(int v=0;v<=n*n+1;v++)        {            if(pre[v]==-1 && mpt[u][v]>0)            {                pre[v]=u;                if(v==des) return 1;                q.push(v);            }        }    }    return 0;}int EK(){    int maxflow=0;    while(bfs())    {        int minflow=INF;        for(int i=des;i!=src;i=pre[i])            minflow=min(minflow,mpt[pre[i]][i]);        maxflow+=minflow;        for(int i=des;i!=src;i=pre[i])        {            mpt[pre[i]][i]-=minflow;            mpt[i][pre[i]]+=minflow;        }    }    return maxflow;}int main(){    int i,j,k;    while(scanf("%d",&n)!=EOF)    {        sum=0;        memset(mpt,0,sizeof(mpt));        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                scanf("%d",&map[i][j]);                sum+=map[i][j];            }        }        src=0;        des=n*n+1;        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                if((i+j)%2==0) mpt[src][(i-1)*n+j]=map[i][j];                else mpt[(i-1)*n+j][des]=map[i][j];            }        }        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                if((i+j)%2==0)                {                    for(k=0;k<4;k++)                    {                        int x=i+dir[k][0];                        int y=j+dir[k][1];                        if(x>=1 && x<=n && y>=1 && y<=n)                        {                            mpt[(i-1)*n+j][(x-1)*n+y]=INF;                        }                    }                }            }        }        printf("%d\n",sum-EK());    }    return 0;}