1001: [BeiJing2006]狼抓兔子
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 7530 Solved: 1724
[Submit][Status]
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
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
HINT
Source
分析：根据题意很容易想到是(1,1)到(n,m)最大流，但最多会有10^6点，普通的会TLE。本屌丝当然也没招~~搜了题解，原来是2008周冬的集训队论文里提到的平面图的最大流——>最小割——>对偶图的最短路，于是可以最短路做，我用的是dijkstra+heap
题解：关于平面图的最大流详见周冬的论文（AH的oier呢好骄傲~~~），这里我只想提一下，根据平面图的定义，几乎所有最大流问题都可以这样做，当然前提是容易判断各个面，目前我见到的只是这种网格网络流，求大神分享其他的……
然后这题只剩建图了：大家自己在草稿纸画画就行了，我是将s点定为0，t点定为(n-1)*(m-1)*2+1（因为里面有(n-1)*(m-1)*2的三角形面），然后就是按顺序给里面的三角形编号，从左到右从上到下编号。然后有左边界或者下边界的连向s，有上边界或者右边界的连向t，中间的处理画画图谢谢式子就行了，具体看我程序
注意：1、建图的时候左下角会连2次s，右上角会连2次t，所以要判重，取两条边中最小的
2、特判m=1或n=1,ans是输入的数中的最小值
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=;
const int maxm=;
const int inf=;
struct heap
{
int d,u;
bool operator < (const heap& x) const
{
return d>x.d;
}
};
priority_queue<heap> q;
struct wjmzbmr
{
int to,data;
};
vector<wjmzbmr> g[(maxn-)*(maxm-)*+];
int n,m,d[(maxn-)*(maxm-)*+],f[(maxn-)*(maxm-)*+];
void ins(int a,int b,int w)
{
g[a].push_back({b,w});
g[b].push_back({a,w});
}
int main()
{ scanf("%d%d",&n,&m);
for(int i=;i<=(maxn-)*(maxm-)*+;++i) g[i].clear();
if(n==&&m==)
{
printf("");
return ;
}
if(n==)
{
int s=inf,x;
for(int i=;i<m;++i) scanf("%d",&x),s=min(s,x);
printf("%d",s);
return ;
}
if(m==)
{
int s=inf,x;
for(int i=;i<n;++i) scanf("%d",&x),s=min(s,x);
printf("%d",s);
return ;
}
int s=,t=(n-)*(m-)*+,a=inf,b=inf;
for(int i=;i<=n;++i)
for(int j=;j<m;++j)
{
int x;
scanf("%d",&x);
if(i==&&j==m-)
{
a=min(x,a);
continue;
}
if(i==n&&j==)
{
b=min(x,b);
continue;
}
if(i==) ins(j,t,x);
if(i==n) ins((n-)*(m-)*+m-+j,s,x);
if(i!=&&i!=n) ins(*(i-)*(m-)+m-+j,*(i-)*(m-)+j,x); }
for(int i=;i<=n-;++i)
for(int j=;j<=m;++j)
{
int x;
scanf("%d",&x);
if(i==&&j==m)
{
a=min(x,a);
continue;
}
if(i==n-&&j==)
{
b=min(x,b);
continue;
}
if(j==) ins(s,(i-)**(m-)+m,x);
if(j==m) ins(t,(i-)**(m-)+m-,x);
if(j!=&&j!=m) ins((i-)**(m-)+j-,(i-)**(m-)+m-+j,x);
}
for(int i=;i<=n-;++i)
for(int j=;j<=m-;++j)
{
int x;
scanf("%d",&x);
ins((i-)**(m-)+j,(i-)*(m-)*+m-+j,x);
}
ins(m-,t,a);ins(t-m+,,b);
memset(f,,sizeof(f));
for(int i=s;i<=t;++i) d[i]=inf;d[s]=;
while(!q.empty())q.pop();
q.push({,s});
while(!q.empty())
{
heap x=q.top();q.pop();
if(f[x.u]==) continue;
f[x.u]=;
for(int i=;i<g[x.u].size();++i)
if(d[x.u]+g[x.u][i].data<d[g[x.u][i].to])
{
d[g[x.u][i].to]=d[x.u]+g[x.u][i].data;
q.push({d[g[x.u][i].to],g[x.u][i].to});
}
}
printf("%d",d[t]);
return ;
}