描述 Description
高一一班的座位表是个 n*m 的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的 scp 大老板，想知道如何分配可以使得全班的喜悦值总和最大。
输入格式 InputFormat
第一行两个正整数 n，m。接下来是六个矩阵第一个矩阵为 n 行 m 列 此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j 列的同学选择文科获得的喜悦值。第二个矩阵为 n 行 m 列 此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j 列的同学选择理科获得的喜悦值。第三个矩阵为 n-1 行 m 列 此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j 列的同学与第 i+1 行第 j 列的同学同时选择文科获得的额外喜悦值。第四个矩阵为 n-1 行 m 列 此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j 列的同学与第 i+1 行第 j 列的同学同时选择理科获得的额外喜悦值。第五个矩阵为 n 行 m-1 列 此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j 列的同学与第 i 行第 j+1 列的同学同时选择文科获得的额外喜悦值。第六个矩阵为 n 行 m-1 列 此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j 列的同学与第 i 行第 j+1 列的同学同时选择理科获得的额外喜悦值。
输出格式 OutputFormat
输出一个整数，表示喜悦值总和的最大值
样例输入 SampleInput
2 3
1534 2296 345
551 1429 4085
1488 2707 3095
1198 3778 1811
3571 4832 1658
2894 2742 1118
1690 2112
1279 4179
466 3002
3977 4256
样例输出 SampleOutput
32532
为求最大收益，则把所有可能的获益之和再减去为达到合理方案而减少的最少的收益，所以可得求最小割。分文理科考虑，源点与每个点建边容量为文科收益，每个点向汇点建边容量为理科收益，于是最后所有点会被分成两个集合，S 集合为选文科的，T 集合为选理科的。
对于相邻的同学，若两人选的相同科，则割掉另一科的边，若不同则两科边都需割掉，所以建图为源点向相邻同学建边容量为文科收益一半，相邻同学向汇点建边容量为理科收益一半，之间也建边，容量为文理各一半之和。为了精度先乘以二处理最后答案再除以二。
自己的程序时间不忍直视。。。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define id(x,y) ((x-1)*m+y)
const int inf = 0x7fffffff;
const int maxn = 105 * 105;
const int maxm = maxn * 30;
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};//R,L,D,U
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, fl, nx;
} e[maxm];
int head[maxn], dis[maxn], used[maxn], cur[maxn];
int cnt, num, ans;
int a[105][105][5];
deque <int> q;
inline void ins(int u, int v, int f)
{
e[cnt] = (edge)
{
v, f, head[u]
}; head[u] = cnt++;
e[cnt] = (edge)
{
u, 0, head[v]
}; head[v] = cnt++;
}
inline bool bfs(int s, int t, int tim)
{
int i, u, v;
while (!q.empty()) q.pop_front();
dis[s] = 0; used[s] = tim;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front();
for (i = head[u]; i != -1; i = e[i].nx)
{
v = e[i].to;
if (used[v] != tim && e[i].fl > 0)
{
used[v] = tim;
dis[v] = dis[u] + 1;
q.push_back(v);
}
}
}
return (used[t] == tim);
}
int dfs(int u, int t, int flow)
{
int v, d, f = flow;
if (u == t) return flow;
for (int &i = cur[u]; i != -1 && f > 0; i = e[i].nx)
{
v = e[i].to;
if (dis[v] == dis[u] + 1 && e[i].fl > 0)
{
d = dfs(v, t, min(f, e[i].fl));
e[i].fl -= d; e[i ^ 1].fl += d;
f -= d;
}
}
return flow - f;
}
inline void dinic(int s, int t)
{
while (bfs(s, t, ++num))
{
memcpy(cur, head, sizeof(head));
ans -= dfs(s, t, inf);
}
printf("%d\n", ans >> 1);
}
int main()
{
cnt = num = ans = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
scanf("%d", &x);
x <<= 1;
ans += x;
ins(0, id(i, j), x);
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
scanf("%d", &x);
x <<= 1;
ans += x;
ins(id(i, j), n * m + 1, x);
}
for (i = 1; i < n; i++)
for (j = 1; j <= m; j++)
{
scanf("%d", &x);
ans += x << 1;
ins(0, id(i, j), x);
ins(0, id(i + 1, j), x);
a[i][j][3] = a[i + 1][j][4] += x;
}
for (i = 1; i < n; i++)
for (j = 1; j <= m; j++)
{
scanf("%d", &x);
ans += x << 1;
ins(id(i, j), n * m + 1, x);
ins(id(i + 1, j), n * m + 1, x);
a[i][j][3] = a[i + 1][j][4] += x;
}
for (i = 1; i <= n; i++)
for (j = 1; j < m; j++)
{
scanf("%d", &x);
ans += x << 1;
ins(0, id(i, j), x);
ins(0, id(i, j + 1), x);
a[i][j][1] = a[i][j + 1][2] += x;
}
for (i = 1; i <= n; i++)
for (j = 1; j < m; j++)
{
scanf("%d", &x);
ans += x << 1;
ins(id(i, j), n * m + 1, x);
ins(id(i, j + 1), n * m + 1 , x);
a[i][j][1] = a[i][j + 1][2] += x;
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
for (k = 1; k <= 4; k++)
{
x = i + dx[k]; y = j + dy[k];
if (x > 0 && x <= n && y > 0 && y <= m) ins(id(i, j), id(x, y), a[i][j][k]);
}
dinic(0, n * m + 1);
return 0;
}