HDU 1569 方格取数(2)

方格取数(2)

Time Limit: 5000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 1569
64-bit integer IO format: %I64d Java class name: Main

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

Input

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

Output

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

Sample Input

Sample Output

Source

Happy 2007

解题：最大点权独立集 = sum - 最小点权独立集

　　最小点权独立集 = 最小割 = 最大流。

　　黑白棋盘。i+j为偶数的点，直接与超级汇点连接，权值为改点的权值。i+j为奇数的点，与超级源点连接，权值为该点权值。并且，同时与它的相邻四个方向的点连接，权值为无限大。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 3000;
18 struct arc {
19     int to,flow,next;
20     arc(int x = 0,int y = 0,int z = 0) {
21         to = x;
22         flow = y;
23         next = z;
24     }
25 };
26 arc e[maxn*10];
27 int head[maxn],d[maxn],tot;
28 int S,T,q[maxn],hd,tail,n,m;
29 void add(int u,int v,int flow) {
30     e[tot] = arc(v,flow,head[u]);
31     head[u] = tot++;
32     e[tot] = arc(u,0,head[v]);
33     head[v] = tot++;
34 }
35 bool bfs() {
36     for(int i = 1; i <= T; i++) d[i] = 0;
37     d[S] = 1;
38     hd = tail = 0;
39     q[tail++] = S;
40     while(hd < tail) {
41         int u = q[hd++];
42         for(int i = head[u]; ~i; i = e[i].next) {
43             if(e[i].flow && !d[e[i].to]) {
44                 d[e[i].to] = d[u]+1;
45                 q[tail++] = e[i].to;
46             }
47         }
48     }
49     return d[T];
50 }
51 int dfs(int u,int low) {
52     int tmp = 0,f;
53     if(u == T || !low) return low;
54     for(int i = head[u]; ~i; i = e[i].next) {
55         if(d[e[i].to] == d[u]+1 && (f = dfs(e[i].to,min(low,e[i].flow)))) {
56             tmp += f;
57             e[i].flow -= f;
58             e[i^1].flow += f;
59             low -= f;
60             if(!low) break;
61         }
62     }
63     return tmp;
64 }
65 int main() {
66     while(~scanf("%d %d",&n,&m)) {
67         memset(head,-1,sizeof(head));
68         int sum = tot = 0,o,ans = 0;
69         S = n*m+1;
70         T = n*m+2;
71         for(int i = 1; i <= n; i++)
72             for(int j = 1; j <= m; j++) {
73                 scanf("%d",&o);
74                 sum += o;
75                 int tmp = (i-1)*m + j;
76                 if((i+j)&1) {
77                     add(S,tmp,o);
78                     if(i > 1) add(tmp,tmp-m,INF);
79                     if(j > 1) add(tmp,tmp-1,INF);
80                     if(i < n) add(tmp,tmp+m,INF);
81                     if(j < m) add(tmp,tmp+1,INF);
82                 } else add(tmp,T,o);
83             }
84         while(bfs()) ans += dfs(S,INF);
85         printf("%d
",sum-ans);
86     }
87     return 0;
88 }

View Code