Description
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形： 
左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角(1,1)的窝里，现在它们要跑到右下解(N,M)的窝中去，狼王开始伏击这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.
Input
第一行为N,M.表示网格的大小，N,M均小于等于1000.接下来分三部分第一部分共N行，每行M-1个数，表示横向道路的权值. 第二部分共N-1行，每行M个数，表示纵向道路的权值. 第三部分共N-1行，每行M-1个数，表示斜向道路的权值. 输入文件保证不超过10M
Output
输出一个整数，表示参与伏击的狼的最小数量.
Sample Input
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
Sample Output
14
这个题很简单噻，求对偶图然后单源最短路，，
我来讲一下，，平面图的最大流，就是最小割噻，，那么我们就是要找到一个割把该图割成两半，
分别包含源点汇点，，所以我们就是要找到一条从左下到右上的最短路，，
所以我们把每一个封闭区域当做一个点，两个区域的临边就是两点之间的距离，，
讲到这里七窍以通六窍，接下来的可以忽略。。。
然后求左下到右上的最短路噻~~我们可以以0为起点，把左下方的最外层的边与0相连，，右上方同理建一个终点，，
然后dijkstra+heap得解，，
AC代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
#define SIZE 3000000
#define inf 0x7fffffff
struct node{
int to,l,last;
}edge[SIZE];
bool operator<(const node &a,const node &b){
return a.l > b.l;
}
int last[SIZE],top,ans,n,m,maxsize;
int dist[SIZE];
bool vis[SIZE];
priority_queue<node> Q;
int addline(int i,int j,int l){
edge[++top].to = j;
edge[top].l = l;
edge[top].last = last[i];
last[i] = top;
}
void PUSH(int to,int l){
node x;
x.to = to;
x.l = l;
Q.push(x);
}
int right_up(int i,int j){
if ( i <= 1 || j >= m )
return maxsize;
if ( i > n || j < 1 )
return 0;
return (n-1)*(m-1)+(i-2)*(m-1)+j;
}
int right_down(int i,int j){
if ( i < 1 || j >= m )
return maxsize;
if ( i >= n || j < 1 )
return 0;
return (i-1)*(m-1)+j;
}
int heng(int i,int j,int l){
int a = right_up(i,j);
int b = right_down(i,j);
addline(a,b,l);
addline(b,a,l);
}
int shu(int i,int j,int l){
int a = right_up(i+1,j);
int b = right_down(i,j-1);
addline(a,b,l);
addline(b,a,l);
}
int xie(int i,int j,int l){
int a = right_up(i+1,j);
int b = right_down(i,j);
addline(a,b,l);
addline(b,a,l);
}
int dijkstra(){
// Q.nul();
for (int i = 0; i <= maxsize; i++){
vis[i] = false;
dist[i] = inf;
}
dist[0] = 0;
PUSH(0,0);
while(!Q.empty()){
node x = Q.top(); Q.pop();
int end = x.to;
int dis = x.l;
// printf("Get %d dist %d\n",end,dis);
if ( vis[end] == true )
continue;
if ( end == maxsize )
break;
vis[end] = true;
for (int wh = last[end];wh;wh = edge[wh].last){
int to = edge[wh].to;
if ( vis[to] == false && dist[to] > dist[end]+edge[wh].l ){
dist[to] = dist[end] + edge[wh].l;
PUSH(to,dist[to]);
}
}
}
ans = dist[maxsize];
return ans;
}
void read(){
scanf("%d%d",&n,&m);
if ( n == 1 && m == 1 ){
// printf("0");
exit(0);
}
maxsize = 2*(n-1)*(m-1)+1;
int l;
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++){
scanf("%d",&l);
heng(i,j,l);
}
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++){
scanf("%d",&l);
shu(i,j,l);
}
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
{
scanf("%d",&l);
xie(i,j,l);
}
}
int work(){
return dijkstra();
}
void print(){
printf("%d\n",ans);
}
int main(){
read();
work();
print();
return 0;
}