方格取数(2)

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3923 Accepted Submission(s): 1227

Problem Description 给你一个m*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。
Input 包括多个测试实例，每个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50)
Output 对于每个测试实例，输出可能取得的最大的和
Sample Input

Sample Output

解题思路；根据奇偶建图，加源点汇点，假如（i+j）是奇数，从源点向这个点连边，否则从这个点向汇点连边，对于每一个奇数点，向四周偶数点连边。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-23 18:24:41
File Name :\acm\代码\1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; #define inf 0x3f3f3f3f const int maxn=10000; int head[maxn],tol,dep[maxn],n; struct node { int next,to,from,cap; }edge[300000]; void add(int u,int v,int cap) { edge[tol].from=u; edge[tol].to=v; edge[tol].cap=cap; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].cap=0; edge[tol].next=head[v]; head[v]=tol++; } int bfs(int s,int t) { int que[maxn],front=0,rear=0; memset(dep,-1,sizeof(dep)); dep[s]=0;que[rear++]=s; while(front!=rear) { int u=que[front++];front%=maxn; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap>0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; rear%=maxn; if(v==t)return 1; } } } return 0; } int dinic(int s,int t) { int i,res=0,top; int Stack[maxn],cur[maxn]; while(bfs(s,t)) { memcpy(cur,head,sizeof(head)); int u=s;top=0; while(1) { if(u==t) { int min=inf,loc; for(int i=0;i
              
               edge[Stack[i]].cap) { min=edge[Stack[i]].cap; loc=i; } for(int i=0;i
               
                1)add(id(i,j),id(i,j-1),inf); if(i>1)add(id(i,j),id(i-1,j),inf); if(i

hdu 1569 最大流建图

方格取数(2)