题目大意：在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，输出这些数之和的最大值。
思路：这种各个点之间互相排斥求最大值的题，往往需要利用上网络流最小割的性质。我们把方格中的所有数字都选上，看看把哪些格子抠掉，能使数值和的减少量最少。
每个格子看作一个节点，其向四周的格子代表的节点连边。现要求一个节点的集合，使得这些点与所有边相连，求点权之和最小值。这就是最小权点覆盖集问题。
要想使该问题有解，往往要将图中的节点分为两个集合，一个集合内的任意两个节点之间没有边相连，也就是说图中所有边两头的节点必须属于不同的集合。解决该问题方法为将S与一个集合中的所有点相连，将另一个集合中的所有点与汇点相连，原图中的边容量设为无穷大，然后跑一遍最大流即可。
理解：每条连接两个集合的边两边的节点我们只要选一个抠掉，两个集合即可彻底分开。这条边的容量是无穷大，即可保证两个 连接两个集合的边的两端节点 与 源汇 连的边中 只会容量小的那个满流，表示选择了这条节点。这样，此时的最大流（最小割）便是最小点权之和。
本题中，我们发现如果把方格按照国际象棋棋盘那样的方式决定节点的集合，恰好满足要求。
#include <cstdio> #include <cassert> #include <cstring> #include <queue> #include <algorithm> #include <cmath> using namespace std; #define LOOP(i, n) for(int i=1; i<=n; i++) const int MAX_NODE = 5100, MAX_EDGE = MAX_NODE * 100, INF = 0x3f3f3f3f; struct Dinic { struct Node; struct Edge; struct Node { Edge *Head, *DfsFrom; int Level; }_nodes[MAX_NODE]; int _vCount; Node *Start, *Target; struct Edge { Node *To; Edge *Next, *Rev; int Cap; Edge(Node *to, Edge *next, int cap):To(to),Next(next),Cap(cap){} }*_edges[MAX_EDGE]; int _eCount; void Init(int vCount, int sId, int tId) { _vCount = vCount; Start = sId + _nodes; Target = tId + _nodes; _eCount = 0; } Edge *AddEdge(Node *from, Node *to, int cap) { Edge *e = _edges[++_eCount] = new Edge(to, from->Head, cap); from->Head = e; return e; } void Build(int uId, int vId, int cap) { Node *u = uId + _nodes, *v = vId + _nodes; Edge *e1 = AddEdge(u, v, cap), *e2 = AddEdge(v, u, 0); e1->Rev = e2; e2->Rev = e1; } bool Bfs() { static queue<Node*> q; LOOP(i, _vCount) _nodes[i].Level = 0; Start->Level = 1; q.push(Start); while (!q.empty()) { Node *u = q.front(); q.pop(); for (Edge *e = u->Head; e; e = e->Next) { if (!e->To->Level && e->Cap) { e->To->Level = u->Level + 1; q.push(e->To); } } } return Target->Level; } int Dfs(Node *cur, int limit) { if (cur == Target) return limit; if (limit == 0) return 0; int curTake = 0; for (Edge *e = cur->DfsFrom; e; cur->DfsFrom = e = e->Next) { if (e->To->Level == cur->Level + 1 && e->Cap) { int nextTake = Dfs(e->To, min(limit - curTake, e->Cap)); e->Cap -= nextTake; e->Rev->Cap += nextTake; curTake += nextTake; } if (limit - curTake==0) break; } return curTake; } int Proceed() { int ans = 0; while (Bfs()) { LOOP(i, _vCount) _nodes[i].DfsFrom = _nodes[i].Head; ans += Dfs(Start, INF); } return ans; } }g; int main() { #ifdef _DEBUG freopen("c:\noi\source\input.txt", "r", stdin); #endif const int direct[][2] = { {-1,0},{0,1},{1,0},{0,-1} }; int totCol, totRow, sId, tId, totSum = 0; static int matrix[110*110]; scanf("%d%d", &totCol, &totRow); sId = totCol*totRow + 1; tId = totCol*totRow + 2; g.Init(tId, sId, tId); LOOP(col, totCol) LOOP(row, totRow) { int cur = (col - 1)*totRow + row; scanf("%d", &matrix[cur]); totSum += matrix[cur]; if ((row + col - 1) % 2) g.Build(sId, cur, matrix[cur]); else g.Build(cur, tId, matrix[cur]); } LOOP(col, totCol) LOOP(row, totRow) if ((row + col -1 ) % 2) { int cur = (col - 1)*totRow + row; for (int i = 0; i < 4; i++) { int col2 = col + direct[i][0], row2 = row + direct[i][1]; if (col2 >= 1 && col2 <= totCol&&row2 >= 1 && row2 <= totRow) { int next = totRow*(col2 - 1) + row2; g.Build(cur, totRow*(col2 - 1) + row2, INF); } } } int subt = g.Proceed(); printf("%d ", totSum - subt); return 0; }
注意：
1.判断方格的上下左右这方面，尽量分别用两个变量表示行和列。直观，不容易出错。
2.先系统连与源汇相连的边，再连两个集合间的边。错误做法：站在一个集合上，找能连到另一个集合的节点的边，将其构造，然后将令那个另一个集合的节点与汇点相连。因为一个集合的点有多条边，每次把另一个集合的节点与汇点相连造成了很多重边。