1 /*  2 最大点权独立集=总权值-最小点权覆盖集  3 最大点权独立集=最大流  4 最小点权覆盖集=最小割  5   6 题意：  7 给你一个m*n的格子的棋盘，每个格子里面有一个非负数。  8 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。  9 根据奇偶建立二分图， 10 if(i+j)%2==0 源点和该点连接,权值为该点的点权, 11 if(i+j)%2==1 该点和汇点连接,权值为该点的点权, 12 之后若i+j为偶数的点和i+j为奇数的点之间相邻，那么就连一条从为偶数的点到为奇数的点的边，权值为无穷大 13 */ 14 #include
      
        15 #include
       
         16 #include
        
          17 #include
         
           18 #include
          
            19 #include
           
             20 using namespace std; 21 const int inf = 0x3f3f3f3f; 22 const int maxn = 2605; 23 const int maxm = 30005; 24 const int dx[]={ 1,-1,0,0}; 25 const int dy[]={ 0,0,1,-1}; 26 struct Node{ 27 int u,v,next,val; 28 }edge[ maxm ]; 29 int head[ maxn ],cnt; 30 void init(){ 31 cnt = 0; 32 memset( head,-1,sizeof( head ) ); 33 } 34 void addedge( int a,int b,int c ){ 35 edge[ cnt ].u = a; 36 edge[ cnt ].v = b; 37 edge[ cnt ].val = c; 38 edge[ cnt ].next = head[ a ]; 39 head[ a ] = cnt++; 40 41 edge[ cnt ].u = b; 42 edge[ cnt ].v = a; 43 edge[ cnt ].val = 0; 44 edge[ cnt ].next = head[ b ]; 45 head[ b ] = cnt++; 46 } 47 48 int queue[ maxn ]; 49 int lev[ maxn ]; 50 int Dinic( int start,int end ){ 51 int max_flow = 0; 52 while( true ){ 53 int Head,Tail,id; 54 Head = Tail = 0; 55 queue[ Tail++ ] = start; 56 memset( lev,-1,sizeof( lev ) ); 57 lev[ start ] = 0; 58 while( Head
            
             0&&lev[edge[id].v]==-1 ){ 62 lev[edge[id].v] = lev[edge[id].u]+1; 63 queue[Tail++] = edge[id].v; 64 if( edge[id].v==end ){ 65 Head = Tail; 66 break;//分层完成 67 } 68 } 69 id = edge[id].next; 70 } 71 }//bfs构造层次网络 72 73 if( lev[end]==-1 ) break; 74 75 id = start; 76 Tail = 0; 77 //这里queue被当作stack来用 78 while( true ){ //层次网络中进行dfs 79 if( id==end ){ //dfs找到汇点 80 int flow = inf; 81 int flag = -1; 82 for( int i=0;i
             
              0&&(lev[edge[id].u]+1==lev[edge[id].v]) ){104 break;105 }106 id = edge[id].next;107 }108 if( id!=-1 ){109 queue[Tail++] = id;110 id = edge[id].v;111 }112 else{113 if( Tail==0 ) break;114 lev[ edge[queue[Tail-1]].v ] = -1;115 id = edge[queue[--Tail]].u;116 }117 }118 }119 return max_flow;120 }121 int main(){122 int m,n;123 while( scanf("%d%d",&n,&m)!=EOF ){124 init();125 int sum = 0;126 int temp;127 for( int i=1;i<=n;i++ ){128 for( int j=1;j<=m;j++ ){129 scanf("%d",&temp);130 if( (i+j)%2==0 ){131 addedge( 0,(i-1)*m+j,temp );132 }133 else{134 addedge( (i-1)*m+j,n*m+1,temp );135 }136 sum += temp;137 }138 }139 for( int i=1;i<=n;i++ ){140 for( int j=1;j<=m;j++ ){141 if( (i+j)%2==0 ){142 for( int k=0;k<4;k++ ){143 int tx = i+dx[k];144 int ty = j+dy[k];145 if( tx>=1&&tx<=n&&ty>=1&&ty<=m ){146 addedge( (i-1)*m+j,(tx-1)*m+ty,inf );147 }148 }149 }150 }151 }152 int start = 0;153 int end = n*m+1;154 int ans = Dinic( start,end );155 //printf("sum = %d,ans = %d\n",sum,ans);156 printf("%d\n",sum-ans);157 }158 return 0;159 }