XTU 二分图和网络流练习题 C. 方格取数(1)

C. 方格取数(1)

Time Limit: 5000ms

Memory Limit: 32768KB

64-bit integer IO format: %I64d Java class name: Main

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

Input

包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)

Output

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

Sample Input

Sample Output

188

解题：有人用状态压缩dp做啊，我只能对着别人的代码敲了。。。。。

 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 #define LL long long
13 #define INF 0x3f3f3f3f
14 using namespace std;
15 const int maxn = 510;
16 int mp[maxn*maxn],tot,n,src,sink;
17 int c[maxn][maxn];
18 bool vis[maxn];
19 int dfs(int u,int low){
20     if(u == sink) return low;
21     if(vis[u]) return 0;
22     vis[u] = true;
23     for(int v = 0,flow; v <= sink; v++){
24         if(c[u][v] && (flow = dfs(v,min(low,c[u][v])))){
25             c[u][v] -= flow;
26             c[v][u] += flow;
27             return flow;
28         }
29     }
30     return 0;
31 }
32 int maxFlow(){
33     int ans = 0,flow;
34     memset(vis,false,sizeof(vis));
35     while(flow = dfs(src,INF)){
36         memset(vis,false,sizeof(vis));
37         ans += flow;
38     }
39     return ans;
40 }
41 int main(){
42     int i,j,temp;
43     while(~scanf("%d",&n)){
44         j = n*n;
45         src = tot = 0;
46         sink = j+1;
47         memset(mp,0,sizeof(mp));
48         memset(c,0,sizeof(c));
49         for(i = 1; i <= j; i++){
50             scanf("%d",&temp);
51             tot += temp;
52             if(i <= n) mp[i] = !mp[i-1];
53             else mp[i] = !mp[i-n];
54             if(mp[i]){
55                 if(i%n) c[i][i+1] = INF;//右边
56                 if(i%n != 1) c[i][i-1] = INF;//左边
57                 if(i <= n*(n-1)) c[i][n+i] = INF;//下边
58                 if(i > n) c[i][i-n] = INF;//上边
59                 c[src][i] = temp;
60             }else c[i][sink] = temp;
61         }
62         printf("%d
",tot-maxFlow());
63     }
64     return 0;
65 }