Problem Description
给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
Input
包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例，输出可能取得的最大的和
Sample Input
3
75 15 21
75 15 28
34 70 5
Sample Output
188
预备知识：
对于一个无向图G，点有各自的权值
点覆盖集：一个点集，使G中所有的边至少有一个点在该集合内
最小点权覆盖集：权值和最小的点覆盖集
点独立集：一个点集，该集合中任意两个点都没有边相连
最大点权独立集：全职和最大的点独立集
定理：
1、最小点权覆盖集 = 最小割 = 最大流
2、最大点权独立集 = 总权值 - 最小点权覆盖集
分析：
该题是二分图中的最大点权独立集的题目
可以用网络流来做
将每个格子抽象成一个点，相邻格子分别涂成黑色和白色
将源点和白色点连一条边，权值为白色点的权值
将白点和它所能到达的白点连一条边，权值为INF
将黑点和汇点连一条边，权值为黑点的权值
这样求出来的网络流便是最小点权覆盖集
然后用总权值减去即可
细节处理：将图上的各点先转化为数字，奇数行奇数列上的点跟偶数行偶数列上的点是同色的
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7 8 const int maxn = 205 << 1; 9 const int INF = 1000000000; 10 11 int map[25][25], a[25][25]; 12 int xx[4] = { 0, 0, 1, -1 }; 13 int yy[4] = { 1, -1, 0, 0 }; 14 15 struct Edge 16 { 17 int from, to, cap, flow; 18 }; 19 20 struct Dinic 21 { 22 int n, m, s, t; 23 vector<Edge> edges; 24 vector<int>G[maxn]; 25 bool vis[maxn]; 26 int d[maxn]; 27 int cur[maxn]; 28 29 void ClearAll(int n) { 30 for(int i = 0; i <= n; i++) { 31 G[i].clear(); 32 } 33 edges.clear(); 34 } 35 36 void AddEdge(int from, int to, int cap) { 37 edges.push_back((Edge){from, to, cap, 0} ); 38 edges.push_back((Edge){to, from, 0, 0} ); 39 m = edges.size(); 40 G[from].push_back(m - 2); 41 G[to].push_back(m - 1); 42 //printf("%din end ",m); 43 } 44 45 bool BFS() 46 { 47 memset(vis, 0, sizeof(vis) ); 48 queue<int> Q; 49 Q.push(s); 50 vis[s] = 1; 51 d[s] = 0; 52 while(!Q.empty() ){ 53 int x = Q.front(); Q.pop(); 54 for(int i = 0; i < G[x].size(); i++) { 55 Edge& e = edges[G[x][i]]; 56 if(!vis[e.to] && e.cap > e.flow) { 57 vis[e.to] = 1; 58 d[e.to] = d[x] + 1; 59 Q.push(e.to); 60 } 61 } 62 } 63 return vis[t]; 64 } 65 66 int DFS(int x, int a) { 67 if(x == t || a == 0) return a; 68 int flow = 0, f; 69 for(int& i = cur[x]; i < G[x].size(); i++) { 70 Edge& e = edges[G[x][i]]; 71 if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { 72 e.flow += f; 73 edges[G[x][i]^1].flow -= f; 74 flow += f; 75 a -= f; 76 if(a == 0) break; 77 } 78 } 79 return flow; 80 } 81 82 int MaxFlow(int s, int t) { 83 this -> s = s; this -> t = t; 84 int flow = 0; 85 while(BFS()) { 86 memset(cur, 0, sizeof(cur)); 87 flow += DFS(s, INF); 88 } 89 return flow; 90 } 91 }; 92 93 Dinic g; 94 95 int main() { 96 int n; 97 //freopen("b.txt","r",stdin); 98 while(EOF != scanf("%d",&n) ) { 99 int tot = 1; 100 int sum = 0; 101 int s = 0; int t = n * n + 1; 102 for(int i = 1;i <= n; i++) { 103 for(int j = 1; j <= n; j++) { 104 scanf("%d",&a[i][j]); 105 sum += a[i][j]; 106 map[i][j] = tot++; 107 } 108 } 109 g.ClearAll(maxn); 110 for(int i = 1; i <= n; i++) { 111 for(int j = 1; j <= n; j++) { 112 113 if(i % 2 == 1 && j % 2 == 1) { 114 g.AddEdge(s, map[i][j], a[i][j]); 115 for(int k = 0; k < 4; k++) { 116 int tmpx = i + xx[k]; int tmpy = j + yy[k]; 117 if(tmpx >= 1 && tmpx <= n && tmpy >= 1 && tmpy <= n) { 118 g.AddEdge(map[i][j], map[tmpx][tmpy], INF); 119 //printf("%d %d %d ",tmpx, tmpy, map[tmpx][tmpy]); 120 } 121 } 122 } 123 124 if(i % 2 == 0 && j % 2 == 0) { 125 g.AddEdge(s, map[i][j], a[i][j]); 126 for(int k = 0; k < 4; k++) { 127 int tmpx = i + xx[k]; int tmpy = j + yy[k]; 128 if(tmpx >= 1 && tmpx <= n && tmpy >= 1 && tmpy <= n) { 129 g.AddEdge(map[i][j], map[tmpx][tmpy], INF); 130 } 131 } 132 } 133 134 if(i % 2 == 1 && j % 2 == 0) { 135 g.AddEdge(map[i][j], t, a[i][j]); 136 } 137 if(i % 2 == 0 && j % 2 == 1) { 138 g.AddEdge(map[i][j], t, a[i][j]); 139 } 140 } 141 } 142 //printf("%d %d ",sum, g.MaxFlow(s, t)); 143 printf("%d ",sum - g.MaxFlow(s, t) ); 144 } 145 return 0; 146 }