1001: [BeiJing2006]狼抓兔子

Time Limit: 15 Sec Memory Limit: 162 MB

Submit: 12719 Solved: 3017

[Submit][Status][Discuss]

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

HINT

看着论文学了一下平面图和对偶图

url=1oA7Svl0XEyQmqJgAjE1HKIEUKbqHaoi8qybJYLef5Z646hXs2AETmTQRwfkFBnN4dhouxiwc2YhAQTZSrgWaQqNP-RnhoM7VDdsFz92ziq">《两极相通—浅析最大最小定理在信息学竞赛中的应用》

事实上就是将这个平面图转化成一个对偶图，在这个对偶图上求最短路的长度，就是原来平面图的最小割。

#include<iostream>

#include<cstdio>

#include<cstring>

#define T n*(m-1)+(n-1)*m+(n-1)*(m-1)-n*m+3

using namespace std;

const int N=2001000;

int n,m,point[N],next[N*3],tot=1,ans,dis[N],l[10000000];

struct S{

    int st,en,va;

}aa[N*3];

bool f[N];

inline void add(int x,int y,int z)

{

    tot+=1,next[tot]=point[x];point[x]=tot;

    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;

    tot+=1,next[tot]=point[y];point[y]=tot;

    aa[tot].st=y;aa[tot].en=x;aa[tot].va=z;

}

inline int SPFA(int x,int y)

{

    int h=1,t=1,u,i;

    memset(dis,127/3,sizeof(dis));

    memset(f,1,sizeof(f));

    l[h]=x;dis[x]=0;

    while(h<=t){

        u=l[h];

        f[u]=true;

        for(i=point[u];i;i=next[i])

          if(dis[aa[i].en]>dis[u]+aa[i].va){

            dis[aa[i].en]=dis[u]+aa[i].va;

            if(f[aa[i].en]){

                f[aa[i].en]=false;

                t+=1;

                l[t]=aa[i].en;

            }

          }

        h+=1;

    }

    return dis[y];

}

int main()

{

    int i,j,x,y,z;

    scanf("%d%d",&n,&m);

    ans=210000000;

    for(i=1;i<=n;++i)

      for(j=1;j<m;++j){

        scanf("%d",&x);

        if(n==1) ans=min(ans,x);

        if(i==1) add(1,j*2+1,x);

        else if(i==n) add((i-2)*(m-1)*2+j*2,T,x);

        else add((i-2)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2+1,x);

      }

    for(i=1;i<n;++i)

      for(j=1;j<=m;++j){

        scanf("%d",&x);

        if(m==1) ans=min(ans,x);

        if(j==1) add((i-1)*(m-1)*2+2,T,x);

        else if(j==m) add(1,i*(m-1)*2+1,x);

        else add((i-1)*(m-1)*2+(j-1)*2+1,(i-1)*(m-1)*2+j*2,x);

      }

    for(i=1;i<n;++i)

      for(j=1;j<m;++j){

        scanf("%d",&x);

        add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2+1,x);

      }

    if(n==1&&m==1) ans=0;

    if(n==1||m==1) printf("%d\n",ans);

    else printf("%d\n",SPFA(1,T));

}