[BeiJing2006]狼抓兔子

[BeiJing2006]狼抓兔子

Time Limit:15000MS  Memory Limit:165536K
Total Submit:762 Accepted:164
Case Time Limit:4000MS

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

Sample Output

14

Source
这题一看就是最小割问题,但范围怎么这么大囧。。。后来看了周冬神牛的论文(2008年的那个)才知道原来平面图的最小割等于对偶图的最短路囧。。构图很麻烦,搞得我累死囧。。

#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)
using namespace std;
const int maxn=1000,maxv=maxn*maxn*2,inf=~0U>>2;
int n,m,vs,vt,v;
int Node[maxn][maxn][2];
int Dist[maxv];
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
struct State
{
int p,c;
State(int _p,int _c):p(_p),c(_c){}
bool operator<(const State&o)const
{
return c>o.c;
}
};
vector<Edge> E[maxv];
priority_queue<State> Q;
typedef vector<Edge>::iterator eit;
int Dijstra()
{
rep(i,v)Dist[i]=inf;Q.push(State(vs,0));
while(Q.size())
{
State t=Q.top();Q.pop();if(t.c>Dist[t.p])continue;
if(t.p==vt)return t.c;
tr(e,E[t.p])
{
int ncost=t.c+e->c;
if(ncost<Dist[e->t])
{
Dist[e->t]=ncost;
Q.push(State(e->t,ncost));
}
}
}
}
void AddEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));
E[t].pb(Edge(s,c));
}
int main()
{
//freopen("in","r",stdin);
scanf("%d%d",&n,&m);v=0;
rep(i,n-1)rep(j,m-1)rep(k,2)Node[i][j][k]=v++;
vs=v++;vt=v++;int c;
rep(j,m-1)scanf("%d",&c),AddEdge(vs,Node[0][j][0],c);
rep(i,n-2)rep(j,m-1)
{
scanf("%d",&c);AddEdge(Node[i][j][1],Node[i+1][j][0],c);
}
rep(j,m-1)scanf("%d",&c),AddEdge(Node[n-2][j][1],vt,c);
rep(i,n-1)
{
scanf("%d",&c);AddEdge(Node[i][0][1],vt,c);
rep(j,m-2)
{
scanf("%d",&c);AddEdge(Node[i][j+1][1],Node[i][j][0],c);
}
scanf("%d",&c);AddEdge(vs,Node[i][m-2][0],c);
}
rep(i,n-1)
rep(j,m-1)
{
scanf("%d",&c);
AddEdge(Node[i][j][0],Node[i][j][1],c);
}
printf("%dn",Dijstra());
}

16 thoughts on “[BeiJing2006]狼抓兔子

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>