题目链接：
题目分析
首先，每个人要么学文科，要么学理科，所以可以想到是一个最小割模型。
我们就确定一个人如果和 S 相连就是学文，如果和 T 相连就是学理。
那么我们再来确定建图。首先使用最小割，就是先加上所有可能获得的权值，再减去最小割（即不能获得的权值）。
如果一个人学理，就要割掉与 S 相连的边，那么就是要割掉学文的收益。于是，对于每个点，从 S 向它连边，权值为它学文的收益。
同理，对于每个点，从它向 T 连边，权值为它学理的收益。
对于两个相邻的人，他们有同时学文的收益和同时学理的收益。
如果他们都学文，就会失去同时学理的收益，于是从他们分别向 T 连边，权值为他们同时学理收益的一半。
同理，从 S 向他们分别连边，权值为他们同时学文收益的一半。
但是如果一个人学文一个人学理，就要失去同时学文和同时学理的收益，因此，在他们之前连双向边，权值为同时学文的收益加同时学理的收益的一半。
这样建图，就巧妙地实现了控制不同的收益。
由于建图的时候权值的一半可能不是整数，先将权值乘 2 ，最后再除以 2 。
代码
#include#include #include #include #include #include using namespace std;const int MaxN = 100 + 5, MaxNode = 10000 + 15, INF = 999999999;int n, m, Sum, S, T, Tot, MaxFlow;int Idx[MaxN][MaxN], Wk[MaxN][MaxN][5], Lk[MaxN][MaxN][5], Num[MaxNode], d[MaxNode];struct Edge{ int v, w; Edge *Next, *Other;} E[MaxNode * 12], *P = E, *Point[MaxNode], *Last[MaxNode];inline void AddEdge(int x, int y, int z){ Edge *Q = ++P; ++P; P -> v = y; P -> w = z; P -> Next = Point[x]; Point[x] = P; P -> Other = Q; Q -> v = x; Q -> w = 0; Q -> Next = Point[y]; Point[y] = Q; Q -> Other = P;}inline int gmin(int a, int b) {return a < b ? a : b;}int DFS(int Now, int Flow) { if (Now == T) return Flow; int ret = 0; for (Edge *j = Last[Now]; j; j = j -> Next) if (j -> w && d[Now] == d[j -> v] + 1) { Last[Now] = j; int p = DFS(j -> v, gmin(j -> w, Flow - ret)); ret += p; j -> w -= p; j -> Other -> w += p; if (ret == Flow) return ret; } if (d[S] >= Tot) return ret; if (--Num[d[Now]] == 0) d[S] = Tot; ++Num[++d[Now]]; Last[Now] = Point[Now]; return ret;}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) Idx[i][j] = (i - 1) * m + j; S = n * m + 1; T = n * m + 2; Tot = T; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &Wk[i][j][0]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &Lk[i][j][0]); for (int i = 1; i <= n - 1; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &Wk[i][j][1]); for (int i = 1; i <= n - 1; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &Lk[i][j][1]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m - 1; ++j) scanf("%d", &Wk[i][j][2]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m - 1; ++j) scanf("%d", &Lk[i][j][2]); int v1, v2, v3; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { Sum += Wk[i][j][0] + Wk[i][j][1] + Wk[i][j][2]; Sum += Lk[i][j][0] + Lk[i][j][1] + Lk[i][j][2]; v1 = Wk[i][j][0] * 2 + Wk[i][j][1] + Wk[i][j][2]; v2 = Lk[i][j][0] * 2 + Lk[i][j][1] + Lk[i][j][2]; v1 += Wk[i - 1][j][1]; v2 += Lk[i - 1][j][1]; v1 += Wk[i][j - 1][2]; v2 += Lk[i][j - 1][2]; AddEdge(S, Idx[i][j], v1); AddEdge(Idx[i][j], T, v2); if (i < n) { v3 = Wk[i][j][1] + Lk[i][j][1]; AddEdge(Idx[i][j], Idx[i + 1][j], v3); AddEdge(Idx[i + 1][j], Idx[i][j], v3); } if (j < m) { v3 = Wk[i][j][2] + Lk[i][j][2]; AddEdge(Idx[i][j], Idx[i][j + 1], v3); AddEdge(Idx[i][j + 1], Idx[i][j], v3); } } MaxFlow = 0; memset(d, 0, sizeof(d)); memset(Num, 0, sizeof(Num)); Num[0] = Tot; for (int i = 1; i <= Tot; ++i) Last[i] = Point[i]; while (d[S] < Tot) MaxFlow += DFS(S, INF); Sum -= MaxFlow >> 1; printf("%d\n", Sum); return 0;}