HDU1569+最大点权集

  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<stdio.h>
 15 #include<string.h>
 16 #include<stdlib.h>
 17 #include<algorithm>
 18 #include<iostream>
 19 #include<math.h>
 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<Tail ){
 59             id = head[ queue[ Head++ ] ];
 60             while( id!=-1 ){
 61                 if( edge[ id ].val>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<Tail;i++ ){
 83                     if( edge[queue[i]].val<flow ){
 84                         flow = edge[queue[i]].val;
 85                         flag = i;
 86                     }
 87                 }//寻找最小的边
 88                 for( int i=0;i<Tail;i++ ){
 89                     edge[ queue[i] ].val -= flow;
 90                     edge[ queue[i]^1 ].val += flow;
 91                 }
 92                 if( flag!=-1 )
 93                 {
 94                     max_flow += flow;
 95                     Tail = flag;
 96                     id = edge[ queue[flag] ].u;
 97                 }
 98                 else
 99                     return inf;
100             }
101             id = head[ id ];
102             while( id!=-1 ){
103                 if( edge[id].val>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
",sum,ans);
156         printf("%d
",sum-ans);
157     }
158     return 0;
159 }
View Code
keep moving...