[文章目录]
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只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.n,m<=1000
看到题目：woc？？？网络流，最大流最小割定理。然后看到数据范围的我眼泪掉下来。使劲想DP状态，然而？？？状态不可描述。不甘心的搜题解吧。看到题目眼睛亮了：（果真是网络流！！），然后点进去，GG，啥玩意啊？？没学过啊。。。
说是网络流的一种特殊模型，叫平面图。就是能把残量网络建的图能够投影到一个平面上，并且边之间没有交叉的图。可以转化成最短路来解。
证明过程是这样的：
首先，我们知道最大流最小割定理，那么问题转化成求这个图的最小割。也就是去掉和流量最少的边集能够使s->t没有路径。假想，这是一个平面图，那么边就相当于一堵墙，你需要在一侧，打通和权值最小的墙使得两边联通，也就是原图中间被截断。那么？？？构造一个新图，将平面图的边与边之间的空白空间看为点，边看做连接两个空间的无向边【注意是无向边】，流量不变。（据说这叫平面图转对偶图）那么，最小割就是使两边无穷远处空白联通的最短路。（神机智QWQ）。
难点？？？建图啊，空间的标号啊，看出来是网络流最大流问题啊。。。
这道题，显然，答案就是原图的最小割。还是个平面图，求呗。注意n=1,m=1时，s直接连向t。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,s,t,dis[2001000];
bool v[2001000];
int head[2001000],to[6001000],nxt[6001000],data[6001000],cnt;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
to[++cnt]=x;
nxt[cnt]=head[y];
head[y]=cnt;
data[cnt]=z;
}
queue<int>q;
void spfa()
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;q.push(s);v[s]=1;
while(!q.empty())
{
int x=q.front();q.pop();v[x]=0;
for(int i=head[x];i;i=nxt[i])
if(dis[to[i]]>dis[x]+data[i])
{
dis[to[i]]=dis[x]+data[i];
if(!v[to[i]])
{
q.push(to[i]);
v[to[i]]=1;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
if(n==1&&m==1) {printf("0"); return 0;}
s=2000001;t=s+1;
int x;
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
{
scanf("%d",&x);
if(i==1&&i==n) add(s,t,x);
else if(i==1) add(s,(i-1)*2*(m-1)+j,x);
else if(i==n) add((i-2)*2*(m-1)+(m-1)+j,t,x);
else add((i-2)*2*(m-1)+m-1+j,(i-1)*2*(m-1)+j,x);
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&x);
if(j==1&&j==m) add(s,t,x);
else if(j==1) add((i-1)*2*(m-1)+(m-1)+j,t,x);
else if(j==m) add(s,(i-1)*2*(m-1)+j-1,x);
else add((i-1)*2*(m-1)+(m-1)+j,(i-1)*2*(m-1)+j-1,x);
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{
scanf("%d",&x);
add((i-1)*2*(m-1)+j,(i-1)*2*(m-1)+m-1+j,x);
}
}
spfa();
printf("%d",dis[t]);
return 0;
}