传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1001
顺便推荐一个ppt，里面有对平面图的介绍：浅析最大最小定理在信息学竞赛中的应用。
这里直接求最小割肯定会T，所以应把原图看成一张平面图，ppt中说该平面图对应的对偶图的每一个环对应原图的一个割，这点有些不理解，不过不影响做这一道题。想象一下，在最外面那个无限大的平面，由左上角朝右下角连一条附加的边，这么做就多了一个附加面，设这条附加的边的权值为 -inf，那么最小割一定包含这一条边。把这条边去掉，就成了求一个最短路的问题了。
#include <cstdio>
#include <cstring> const int maxn = 1005, maxnd = maxn * maxn << 1, maxe = maxn * maxn * 3; int n, m, S, T, special = 2147483647, t1, t2, t3;
int head[maxnd], to[maxe << 1], next[maxe << 1], w[maxe << 1], lb;
char ch;
bool inq[maxnd];
int que[maxnd], h, head_, tail, d[maxnd]; inline void ist(int aa, int ss, int ww) {
to[lb] = ss;
next[lb] = head[aa];
head[aa] = lb;
w[lb] = ww;
++lb;
}
inline void readint(int & rt) {
while ((ch = getchar()) < 48);
rt = ch - 48;
while ((ch = getchar()) > 47) {
rt = rt * 10 + ch - 48;
}
} int main(void) {
//freopen("in.txt", "r", stdin);
memset(head, -1, sizeof head);
memset(next, -1, sizeof next);
readint(n); readint(m);
if (n == 1 || m == 1) {
while (scanf("%d", &t1) != EOF) {
special = special < t1? special: t1;
}
printf("%d\n", special);
return 0;
}
S = (n - 1) * (m - 1) * 2 + 1;
T = S + 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
t2 = (i - 1) * (m - 1) * 2 + j * 2;
t1 = t2 - (m - 1) * 2 - 1;
t1 = t1 > 0? t1: T;
t2 = t2 < S? t2: S;
scanf("%d", &t3);
ist(t1, t2, t3);
ist(t2, t1, t3);
}
}
for (int i = 1; i < n; ++i) {
t2 = (i - 1) * (m - 1) * 2 + 1;
scanf("%d", &t3);
ist(S, t2, t3);
ist(t2, S, t3);
for (int j = 2; j < m; ++j) {
t1 = (i - 1) * (m - 1) * 2 + (j - 1) * 2;
t2 = t1 + 1;
scanf("%d", &t3);
ist(t1, t2, t3);
ist(t2, t1, t3);
}
t1 = i * (m - 1) * 2;
scanf("%d", &t3);
ist(t1, T, t3);
ist(T, t1, t3);
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
t2 = (i - 1) * (m - 1) * 2 + j * 2;
t1 = t2 - 1;
scanf("%d", &t3);
ist(t1, t2, t3);
ist(t2, t1, t3);
}
} memset(d, 0x3c, sizeof d);
que[tail++] = S;
inq[S] = true;
d[S] = 0;
while (head_ != tail) {
h = que[head_++];
if (head_ == T) {
head_ = 0;
}
inq[h] = false;
for (int j = head[h]; j != -1; j = next[j]) {
if (d[to[j]] > d[h] + w[j]) {
d[to[j]] = d[h] + w[j];
if (!inq[to[j]]) {
inq[to[j]] = true;
que[tail++] = to[j];
if (tail == T) {
tail = 0;
}
}
}
}
}
printf("%d\n", d[T]);
return 0;
}