Description 在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。 Input 第一行一个数n；（n<=30） 接下来n行每行n个数描述一个方阵 Output 仅一个数，即最大和 Sample Input 2
1 2
3 5
Sample Output 6
解法：
求的显然是最大权独立集，最大权独立集=总权-最小权覆盖集，对于最小权覆盖集我们用最小割来解。
由于取了一个点，不能取上下左右的点，即i+-1 or j+-1，那么显然是一个二分图，根据奇偶分类。
然后就是一个最小割的模型，我们左边的点向上下左右的点连边，容量为INF(必然不是割)，然后跑最大流即
可。
///BZOJ 1475 #include <bits/stdc++.h> using namespace std; const int maxn = 1010; const int maxm = 200010; const int inf = 0x3f3f3f3f; struct G { int v, cap, next; G() {} G(int v, int cap, int next) : v(v), cap(cap), next(next) {} } E[maxm]; int p[maxn], T; int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化，qw队列 void init() { memset(p, -1, sizeof(p)); T = 0; } void add(int u, int v, int cap) { E[T] = G(v, cap, p[u]); p[u] = T++; E[T] = G(u, 0, p[v]); p[v] = T++; } bool bfs(int st, int en, int n) { int i, u, v, head, tail; for(i = 0; i <= n; i++) d[i] = -1; head = tail = 0; d[st] = 0; qw[tail] = st; while(head <= tail) { u = qw[head++]; for(i = p[u]; i + 1; i = E[i].next) { v = E[i].v; if(d[v] == -1 && E[i].cap > 0) { d[v] = d[u] + 1; qw[++tail] = v; } } } return (d[en] != -1); } int dfs(int u, int en, int f) { if(u == en || f == 0) return f; int flow = 0, temp; for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next) { G& e = E[temp_p[u]]; if(d[u] + 1 == d[e.v]) { temp = dfs(e.v, en, min(f, e.cap)); if(temp > 0) { e.cap -= temp; E[temp_p[u] ^ 1].cap += temp; flow += temp; f -= temp; if(f == 0) break; } } } return flow; } int dinic(int st, int en, int n) { int i, ans = 0; while(bfs(st, en, n)) { for(i = 0; i <= n; i++) temp_p[i] = p[i]; ans += dfs(st, en, inf); } return ans; } int n, sum, mp[33][33]; int getid(int x, int y){ return (x-1)*n+y; } int main(){ scanf("%d", &n); for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ scanf("%d", &mp[i][j]); sum += mp[i][j]; } } init(); int source=0, sink=n*n+1; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if((i+j)%2==0){ add(source, getid(i,j), mp[i][j]); if(i>=2) add(getid(i,j), getid(i-1,j), inf); if(j>=2) add(getid(i,j), getid(i,j-1), inf); } if((i+j)%2==1){ add(getid(i,j), sink, mp[i][j]); if(i>=2) add(getid(i-1,j), getid(i,j), inf); if(j>=2) add(getid(i,j-1), getid(i,j), inf); } } } int ans = sum-dinic(source, sink, sink+1); printf("%d\n", ans); return 0; }