题目链接：https://www.oj.swust.edu.cn/problem/show/1744
希望取到的点都是不相邻的（相邻：四连通），那么可以用二分图表示相连关系，然后求最大独立集。
最大独立集就是取的点均不相连，并且权值最大。
给两部分的点从1到n*n标号，源汇点分别连点的容量是对应点的权值，相邻点之间的容量为inf。
用点总权值-最小割即为最大独立集。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef struct Edge { 5 int u, v, w, next; 6 }Edge; 7 8 const int inf = 0x7f7f7f7f; 9 const int maxn = 9090; 10 11 int cnt, dhead[maxn]; 12 int cur[maxn], dd[maxn]; 13 Edge dedge[maxn<<3]; 14 int S, T, N; 15 16 void init() { 17 memset(dhead, -1, sizeof(dhead)); 18 for(int i = 0; i < maxn; i++) dedge[i].next = -1; 19 S = 0; cnt = 0; 20 } 21 22 void adde(int u, int v, int w, int c1=0) { 23 dedge[cnt].u = u; dedge[cnt].v = v; dedge[cnt].w = w; 24 dedge[cnt].next = dhead[u]; dhead[u] = cnt++; 25 dedge[cnt].u = v; dedge[cnt].v = u; dedge[cnt].w = c1; 26 dedge[cnt].next = dhead[v]; dhead[v] = cnt++; 27 } 28 29 bool bfs(int s, int t, int n) { 30 queue<int> q; 31 for(int i = 0; i < n; i++) dd[i] = inf; 32 dd[s] = 0; 33 q.push(s); 34 while(!q.empty()) { 35 int u = q.front(); q.pop(); 36 for(int i = dhead[u]; ~i; i = dedge[i].next) { 37 if(dd[dedge[i].v] > dd[u] + 1 && dedge[i].w > 0) { 38 dd[dedge[i].v] = dd[u] + 1; 39 if(dedge[i].v == t) return 1; 40 q.push(dedge[i].v); 41 } 42 } 43 } 44 return 0; 45 } 46 47 int dinic(int s, int t, int n) { 48 int st[maxn], top; 49 int u; 50 int flow = 0; 51 while(bfs(s, t, n)) { 52 for(int i = 0; i < n; i++) cur[i] = dhead[i]; 53 u = s; top = 0; 54 while(cur[s] != -1) { 55 if(u == t) { 56 int tp = inf; 57 for(int i = top - 1; i >= 0; i--) { 58 tp = min(tp, dedge[st[i]].w); 59 } 60 flow += tp; 61 for(int i = top - 1; i >= 0; i--) { 62 dedge[st[i]].w -= tp; 63 dedge[st[i] ^ 1].w += tp; 64 if(dedge[st[i]].w == 0) top = i; 65 } 66 u = dedge[st[top]].u; 67 } 68 else if(cur[u] != -1 && dedge[cur[u]].w > 0 && dd[u] + 1 == dd[dedge[cur[u]].v]) { 69 st[top++] = cur[u]; 70 u = dedge[cur[u]].v; 71 } 72 else { 73 while(u != s && cur[u] == -1) { 74 u = dedge[st[--top]].u; 75 } 76 cur[u] = dedge[cur[u]].next; 77 } 78 } 79 } 80 return flow; 81 } 82 83 typedef pair<int, int> pii; 84 const int dx[5] = {0, 0, 1, -1}; 85 const int dy[5] = {1, -1, 0, 0}; 86 int n, m, icnt; 87 int G[33][33]; 88 map<pii, int> wobuzhidao; 89 90 inline int id(int x, int y) { 91 return wobuzhidao[pii(x, y)]; 92 } 93 94 inline bool ok(int x, int y) { 95 return x >= 1 && x <= n && y >= 1 && y <= m; 96 } 97 98 int main() { 99 // freopen("in", "r", stdin); 100 int u, v, w; 101 while(~scanf("%d%d",&n,&m)) { 102 init(); wobuzhidao.clear(); icnt = 0; 103 memset(G, 0, sizeof(G)); 104 int sum = 0; 105 for(int i = 1; i <= n; i++) { 106 for(int j = 1; j <= m; j++) { 107 wobuzhidao[pii(i, j)] = ++icnt; 108 scanf("%d", &G[i][j]); 109 sum += G[i][j]; 110 } 111 } 112 S = 0, T = icnt * 2 + 1, N = T + 1; 113 for(int i = 1; i <= n; i++) { 114 for(int j = 1; j <= m; j++) { 115 adde(S, id(i,j), G[i][j]); 116 adde(icnt+id(i,j), T, G[i][j]); 117 for(int k = 0; k < 4; k++) { 118 int x = i + dx[k]; 119 int y = j + dy[k]; 120 if(!ok(x, y)) continue; 121 adde(id(i,j), icnt+id(x,y), inf); 122 } 123 } 124 } 125 int ret = dinic(S, T, N); 126 printf("%d ", sum - ret / 2); 127 } 128 return 0; 129 }