方格取数(2)

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 72 Accepted Submission(s): 35

Problem Description

给你一个m*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。

Input

包括多个测试实例，每个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

Sample Output

Author

ailyanlu

Source

Happy 2007

Recommend

8600

/*
题意：略

初步思路：题目要求的是能取出的最大和，可以换种思路，将相邻的格子都进行建边，然后求出最小割最大流，然后用总数减去这个
    得到的就是想要的结果
*/
#include<bits/stdc++.h>
/****************************************最大流模板****************************************/
#define INF 1e9
using namespace std;
const int maxn=40010;//之前这里只写10+5,一直TLE,真是悲剧

struct Edge
{
    Edge(){}
    Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
    int from,to,cap,flow;
};

struct Dinic
{
    int n,m,s,t;            //结点数,边数(包括反向弧),源点与汇点编号
    vector<Edge> edges;     //边表 edges[e]和edges[e^1]互为反向弧
    vector<int> G[maxn];    //邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
    bool vis[maxn];         //BFS使用,标记一个节点是否被遍历过
    int d[maxn];            //从起点到i点的距离
    int cur[maxn];          //当前弧下标

    void init(int n,int s,int t)
    {
        this->n=n,this->s=s,this->t=t;
        for(int i=0;i<=n;i++) 
            G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,int cap)
    {
        edges.push_back( Edge(from,to,cap,0) );
        edges.push_back( Edge(to,from,0,0) );
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int> Q;//用来保存节点编号的
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty())
        {
            int x=Q.front(); Q.pop();
            for(int i=0; i<G[x].size(); i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow)
                {
                    vis[e.to]=true;
                    d[e.to] = d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a)
    {
        if(x==t || a==0)return a;
        int flow=0,f;//flow用来记录从x到t的最小残量
        for(int& i=cur[x]; i<G[x].size(); i++)
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to] && (f=DFS( e.to,min(a,e.cap-e.flow) ) )>0 )
            {
                e.flow +=f;
                edges[G[x][i]^1].flow -=f;
                flow += f;
                a -= f;
                if(a==0) break;
            }
        }
        return flow;
    }

    int Maxflow()
    {
        int flow=0;
        while(BFS())
        {
            memset(cur,0,sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
}DC;
/****************************************最大流模板****************************************/
int n,m;
int g[55][55];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//用于记录方向数组
int tmp=0;
bool ok(int x,int y){//判断是否出界
    if(x<0||x>=n||y<0||y>=m) return true;
    return false;
}
void init(){
    tmp=0;
}
int main(){
    // freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        DC.init(n*m*2+2,0,n*m*2+1);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%d",&g[i][j]);
                tmp+=g[i][j];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if((i+j)%2==0){
                    //开始遍历四个方向上的方块
                    DC.AddEdge(0,j+i*m+1,INF);
                    DC.AddEdge(j+i*m+1,i*m+j+1+n*m,g[i][j]);
                    for(int k=0;k<4;k++){
                        int fx=i+dir[k][0];
                        int fy=j+dir[k][1];
                        if(ok(fx,fy)) continue;//如果不正常就继续
                        DC.AddEdge(j+i*m+1+n*m,fy+fx*m+1,INF);
                    }
                }else{
                    DC.AddEdge(i*m+j+1 , i*m+j+1+n*m , g[i][j]);
                    DC.AddEdge(i*m+j+1+n*m , n*m*2+1 , INF);
                }
            }
        }
        // cout<<DC.s<<" "<<DC.t<<endl;  
        printf("%d
",tmp-DC.Maxflow());
    }
    return 0;
}