P2030 - 【BJOI2006】狼抓兔子-白红宇

P2030 - 【BJOI2006】狼抓兔子

阅读量：7131 次

发布时间：2019-06-28

本文共 3011 字，大约阅读时间需要 10 分钟。

P2030 - 【BJOI2006】狼抓兔子

Description

八中OJ上本题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1001

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

左上角点为(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

Hint

Source

图论，搜索，最短路径

　暴力就是裸地最大流，但点数与边数都达到了很大的级别，普通的网络流也过不去；可以发现这个题的图是一个平面图：边不会交叉；有一个性质，就是在原图G中，s与t再连一条边得到的较小的那个平面作为s’,最大的面(另一个面)作为t’,做出对偶图：原图中所有面看为点，所有边所相邻的两个面在对偶图所对应的点连一条边，然后从G’中s到t的最短路就是原图的最大流；证明略；

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 14 #define ll long long15 #define rep(i,a,b) for(register int i=a;i<=b;i++)16 #define inf 1<<2917 #define re register18 using namespace std;19 const int N=1000*1000*2,M=1000*1000*3;20 struct Edge{21 int to,net,w;22 }e[M*2];23 int head[N],num_e=-1,n,m;24 int s,t;25 int g[1001][1001][2];26 inline int gi() {27 re int ret=0,f=1;char ch=getchar();28 while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();29 if(ch=='-') f=-1,ch=getchar();30 while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();31 return ret*f;32 }33 inline void add(int x,int y,int w) {34 e[++num_e].to=y,e[num_e].net=head[x],e[num_e].w=w,head[x]=num_e;35 }36 bool inq[N];37 int dis[N];38 int spfa() {39 memset(inq,0,sizeof(inq));40 memset(dis,127/3,sizeof(dis));41 queue
                  
                    q;42 q.push(s);43 inq[s]=1;44 dis[s]=0;45 while(!q.empty()) {46 int u=q.front();q.pop();47 inq[u]=0;48 for(int i=head[u];i!=-1;i=e[i].net) {49 int to=e[i].to;50 if(dis[to] > dis[u]+e[i].w) {51 dis[to]=dis[u]+e[i].w;52 if(!inq[to]) q.push(to),inq[to]=1;53 }54 }55 }56 return dis[t];57 }58 int main() {59 n=gi(),m=gi();60 memset(head,-1,sizeof(head));61 int num=0;62 rep(i,1,n-1)63 rep(j,1,m-1)64 rep(o,0,1)65 g[i][j][o]=++num;66 t=++num,s=0;67 re int w,u,v;68 rep(i,1,n)69 rep(j,1,m-1) {70 w=gi();71 if(i==1) u=g[i][j][0],v=t;72 else if(i==n) u=g[i-1][j][1],v=s;73 else u=g[i-1][j][1],v=g[i][j][0];74 add(u,v,w),add(v,u,w);75 }76 rep(i,1,n-1)77 rep(j,1,m) {78 w=gi();79 if(j==1) u=s,v=g[i][j][1];80 else if(j==m) u=t,v=g[i][j-1][0];81 else u=g[i][j-1][0],v=g[i][j][1];82 add(u,v,w),add(v,u,w);83 }84 rep(i,1,n-1)85 rep(j,1,m-1) {86 w=gi();87 u=g[i][j][0],v=g[i][j][1];88 add(u,v,w),add(v,u,w);89 }90 //cout<<(sizeof(e)+sizeof(head)+sizeof(dis)+sizeof(inq)+sizeof(g))/1024/1024;91 printf("%d",spfa());92 return 0;93 }

转载于:https://www.cnblogs.com/ypz999/p/7118280.html

你可能感兴趣的文章