方格取数(2)

hdu1569:http://acm.hdu.edu.cn/showproblem.php?pid=1569

题意：中文题。

题解：经典的问题。首先，按照(i+j)%2==1和(i+j)%2==0把所有的点分成两部分x，y两部分。分别对于x，和y部分来说，任何取两个数都是不相邻的，所以可以任意去。现在的问题x中取多少个数，y中选取多少个数，是的最终的和最大。所以接下来，如果i,j相邻，则i，j之间建立一边，容量是无穷大。x部分和源点建立一边，y部分与汇点建立一边。这样跑网络流，跑出来的流量就是最大流，也就是最小割，再结合一下最小割的定义，很明显，最终的答案就是总的和-maxflow。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<queue>
  6 #define INF 100000000
  7 using namespace std;
  8 const int N=2612;
  9 const int M=14820;
 10 struct Node{
 11    int v;
 12    int f;
 13    int next;
 14 }edge[M];
 15 int n,m,u,v,cnt,sx,ex;
 16 int head[N],pre[N];
 17 int mp[51][51];//根据题目要求申请
 18 void init(){
 19     cnt=0;
 20     memset(head,-1,sizeof(head));
 21 }
 22 void add(int u,int v,int w){
 23     edge[cnt].v=v;
 24     edge[cnt].f=w;
 25     edge[cnt].next=head[u];
 26     head[u]=cnt++;
 27     edge[cnt].f=0;
 28     edge[cnt].v=u;
 29     edge[cnt].next=head[v];
 30     head[v]=cnt++;
 31 }
 32 bool BFS(){
 33   memset(pre,0,sizeof(pre));
 34   pre[sx]=1;
 35   queue<int>Q;
 36   Q.push(sx);
 37  while(!Q.empty()){
 38      int d=Q.front();
 39      Q.pop();
 40      for(int i=head[d];i!=-1;i=edge[i].next    ){
 41         if(edge[i].f&&!pre[edge[i].v]){
 42             pre[edge[i].v]=pre[d]+1;
 43             Q.push(edge[i].v);
 44         }
 45      }
 46   }
 47  return pre[ex]>0;
 48 }
 49 int dinic(int flow,int ps){
 50     int f=flow;
 51      if(ps==ex)return f;
 52      for(int i=head[ps];i!=-1;i=edge[i].next){
 53         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){
 54             int a=edge[i].f;
 55             int t=dinic(min(a,flow),edge[i].v);
 56               edge[i].f-=t;
 57               edge[i^1].f+=t;
 58             flow-=t;
 59              if(flow<=0)break;
 60         }
 61 
 62      }
 63       if(f-flow<=0)pre[ps]=-1;
 64       return f-flow;
 65 }
 66 int solve(){
 67     int sum=0;
 68     while(BFS())
 69         sum+=dinic(INF,sx);
 70     return sum;
 71 }
 72 int main() {
 73     int sum=0;
 74     while(~scanf("%d%d",&n,&m)){
 75          init();sum=0;
 76          for(int i=1;i<=n;i++){
 77             for(int j=1;j<=m;j++){
 78                  scanf("%d",&mp[i][j]);
 79                  sum+=mp[i][j];
 80                  if((i+j)%2==0){
 81                     add(0,(i-1)*m+j,mp[i][j]);
 82                  }
 83                  else{
 84                     add((i-1)*m+j,n*m+1,mp[i][j]);
 85                  }
 86             }
 87          }
 88          for(int i=1;i<=n;i++){
 89             for(int j=1;j<=m;j++){
 90                if((i+j)%2==0){
 91                   int a=(i-1)*m+j;
 92                   if(i>1)add(a,a-m,INF);
 93                   if(i<n)add(a,a+m,INF);
 94                   if(j>1)add(a,a-1,INF);
 95                   if(j<m)add(a,a+1,INF);
 96                }
 97             }
 98          }
 99          sx=0,ex=n*m+1;
100        printf("%d
",sum-solve());
101     }
102     return 0;
103 }

View Code