题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1001
算法讨论：
1、可以用最大流做，最大流等于最小割。
2、可以把这个图转化其对偶图，然后在对偶图上跑最短路即可。
一个平面图的最小割等价于其对偶图从S到T的最短路。并不是所有的图都有对偶图，平面图也有一定的要求，自己可以百度一下。
代码（用BZOJ的数据测过了，但是在BZOJ上过不去。爆WA，并不知道是为什么，里面有个特判，并不知道有没有用处。）
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cstdio> using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f; int n, cnt, m;
int head[N], que[N], dis[N];
bool vis[N]; struct Edge {
int from, to, dis, next;
}edges[N * ]; void add(int u, int v, int dis) {
++ cnt;
edges[cnt].from = u; edges[cnt].to = v;
edges[cnt].dis = dis; edges[cnt].next = head[u];
head[u] = cnt;
++ cnt;
edges[cnt].from = v; edges[cnt].to = u;
edges[cnt].dis = dis; edges[cnt].next = head[v];
head[v] = cnt;
} void spfa(int s, int t) {
int h = , tail = ;
for(int i = s; i <= t; ++ i) {
dis[i] = inf;
vis[i] = false;
}
vis[s] = true; dis[s] = ;
que[h] = s;
while(h <= tail) {
int x = que[h];
vis[x] = false;
for(int i = head[x]; i; i = edges[i].next) {
int v = edges[i].to;
if(dis[v] > dis[x] + edges[i].dis) {
dis[v] = dis[x] + edges[i].dis;
if(!vis[v]) {
que[++ tail] = v;
vis[v] = true;
}
}
}
++ h;
}
printf("%d\n", dis[t]);
} #define stone int main() {
#ifndef stone freopen("bjrabbit.in", "r", stdin);
freopen("bjrabbit.out", "w", stdout); #endif int tmp, s, t, x, mn = 0x3f3f3f3f;
scanf("%d%d", &n, &m);
s = ; t = (n - ) * (m - ) * + ;
tmp = (m - ) * ;
for(int i = ; i <= n; ++ i) {
for(int j = ; j < m; ++ j) {
scanf("%d", &x);
mn = min(x, mn);
if(i == ) {
add(j * + tmp * (i - ), t, x);
}
else if(i == n) {
add(s, j * + tmp * (i - ) - , x);
}
else {
add(j * + tmp * (i - ), j * + tmp * (i - ) - , x);
}
}
}
for(int i = ; i < n; ++ i) {
for(int j = ; j <= m; ++ j) {
scanf("%d", &x);
mn = min(x, mn);
if(j == ) {
add(s, tmp * (i - ) + , x);
}
else if(j == m) {
add(tmp * i, t, x);
}
else {
add(tmp * (i - ) + * (j - ), tmp * (i - ) + * (j - ) + , x);
}
}
}
for(int i = ; i < n; ++ i) {
for(int j = ; j < m; ++ j) {
scanf("%d", &x);
mn = min(mn, x);
add(tmp * (i - ) + j * , tmp * (i - ) + j * - , x);
}
}
if(n == || m == ) printf("%d\n", mn);
else spfa(s, t); #ifndef stone fclose(stdin); fclose(stdout); #endif return ;
}
1001