题意：动物要逃跑，工作人员要截断从START(左上角)到END（右下角）的道路，每条边权表示拦截该条道路需要多少工作人员。问最少需要多少人才能完成拦截。
通俗地讲，就是把图一分为二所造成消耗的最小值。
这里用最短路的方法解，主要是因为数据量太大，不能用最小割最大流还处理。
手动画一下这种“割”的形式，发现是从一条边到另一条边，即以边为“点”，在边与边之间见“边”，边上的权值为终点v（其实是一条边）的权值。（本来想直接用点权处理的，可coding的时候发现SPFA中的入队出队操作太繁琐，老老实实改边权了）。这里因为是以边为点，所以要对每条边编号，借用了昨天刚学到的ID()函数，很实用的。
最终的方案是整体从左下到右上，把START与END分成两部分。那么就以最左侧、最下侧的所有点为起点，做一遍最短路，求出最上侧、最右侧边所对应d[]数组的最小值，即为答案。
注：
1、因为是以边为点，共有少于n*m*3个“点”，共要建边(n-1)*(m-1)*2*3条“边”
2、不保证code是正确滴，这道题在uva挂了，难得能一次就跑出样例...偶已经很久木有一次AC了= =
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define clr(a,m) memset(a,m,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int MAXN=;
const int INF =1e9; struct Edge{
int v,next,c;
Edge(){}
Edge(int x,int y,int z):v(x),c(y),next(z){}
}edge[MAXN*MAXN*]; int id[MAXN][MAXN][],num;
int grid[MAXN][MAXN][]; int head[MAXN*MAXN*],tol;
int vis[MAXN*MAXN*],inq[MAXN*MAXN*],d[MAXN*MAXN*]; void read(int n,int m)
{
rep(i,,n)
rep(j,,m-)
scanf("%d",&grid[i][j][]);
rep(i,,n-)
rep(j,,m)
scanf("%d",&grid[i][j][]);
rep(i,,n-)
rep(j,,m-)
scanf("%d",&grid[i][j][]);
} void init()
{
tol=;
clr(head,-); num=;
clr(id,);
} void add(int u,int v,int cv,int cu)
{
edge[tol]=Edge(v,cv,head[u]);
head[u]=tol++; edge[tol]=Edge(u,cu,head[v]);
head[v]=tol++;
} int ID(int i,int j,int k)
{
int& x=id[i][j][k];
if(!x)x=++num;
return x;
} void build(int n,int m)//建图：原图在(n-1)*(m-1)个方格中各有两个三角形，在其内部以边为顶点建三角形，共构建(n-1)*(m-1)*2*3条边
{
init();
rep(i,,n-){
rep(j,,m-){
add(ID(i,j,),ID(i,j,),grid[i][j][],grid[i][j][]);
add(ID(i,j,),ID(i,j+,),grid[i][j+][],grid[i][j][]);
add(ID(i,j,),ID(i,j+,),grid[i][j+][],grid[i][j][]); add(ID(i,j,),ID(i,j,),grid[i][j][],grid[i][j][]);
add(ID(i,j,),ID(i+,j,),grid[i+][j][],grid[i][j][]);
add(ID(i,j,),ID(i+,j,),grid[i+][j][],grid[i][j][]);
}
}
} void SPFA(int n,int m)
{
priority_queue<int,vector<int>,greater<int> >q;
clr(inq,);
rep(i,,num)
d[i]=INF;
rep(i,,n-){
int s=id[i][][];
d[s]=grid[i][][];
q.push(s);
vis[s]=true;
}
rep(j,,m-){
int s=id[n][j][];
d[s]=grid[n][j][];
q.push(s);
vis[s]=true;
}
while(!q.empty())
{
int u=q.top();q.pop();
vis[u]=false;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
int c=edge[i].c;
if(d[v]>d[u]+c){
d[v]=d[u]+c;
if(!vis[v]){
q.push(v);
vis[v]=true;
}
}
}
}
} void print(int n,int m,int cnt)
{
int ans=INF;
rep(j,,m-)
ans=min(ans,d[id[][j][]]);
rep(i,,n-)
ans=min(ans,d[id[i][m][]]);
printf("Case %d: Minimum = %d\n",cnt,ans);
} int main()
{
int n,m,cnt=;
while(scanf("%d%d",&n,&m)==&&n)
{
read(n,m);
build(n,m);
SPFA(n,m);
print(n,m,++cnt);
}
return ;
}