【Bzoj】1001狼抓兔子（平面图最小割转对偶图最短路）

　　YEAH

　　题目链接

　　终于做对这道题啦    建图的艰辛难以言表- -

　　顺便说一句我队列转STL啦

　　狼抓兔子的地图符合平面图定义，于是将该图转成对偶图并求出对偶图的最短路即可。

　　这篇博客给了我极大的帮助，现将链接放上

　　xiaoyimi

　　粘上自己的代码

　　

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>

using namespace std;

queue<int> q;

inline long long read(){
long long num=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')    f=-1;
        ch=getchar();
    }
while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
return num*f;
}

struct Edge{
int next,to,val;
}edge[6000020];
int head[2000020],num;
inline void add(int from,int to,int val){
    edge[++num]=(Edge){head[from],to,val};
    head[from]=num;
}

int disa[1002][1002],disb[1002][1002],id[1002][1002][3];
int ID,Start,End;
bool vis[2000200];
int dst[2000200];

int main(){
    memset(dst,127/3,sizeof(dst));
int n=read(),m=read();
    End=n*m+1;
for(int i=1;i<=n;++i)
for(int j=1;j<m;++j)
            disa[i][j]=read();
for(int i=1;i<n;++i)
for(int j=1;j<=m;++j)
            disb[i][j]=read();
if(n==1){
int a=0x7fffffff;
for(int i=1;i<m;++i)    a=min(a,disa[1][i]);
        printf("%d",a);
return 0;
    }
if(m==1){
int a=0x7fffffff;
for(int i=1;i<n;++i)    a=min(a,disb[i][1]);
        printf("%d",a);
return 0;
    }

for(int i=1;i<n;++i)
for(int j=1;j<m;++j){
int x=read();
            id[i][j][1]=++ID;
            id[i][j][2]=++ID;
            add(id[i][j][1],id[i][j][2],x);
            add(id[i][j][2],id[i][j][1],x);
        }
for(int i=1;i<n;++i){
        add(Start,id[i][1][1],disb[i][1]);
        add(id[i][1][1],Start,disb[i][1]);
        add(id[i][m-1][2],End,disb[i][m]);
        add(End,id[i][m-1][2],disb[i][m]);
    }
for(int i=1;i<n;++i)
for(int j=1;j<m-1;++j){
            add(id[i][j][2],id[i][j+1][1],disb[i][j+1]);
            add(id[i][j+1][1],id[i][j][2],disb[i][j+1]);
        }
for(int i=1;i<m;++i){
        add(Start,id[n-1][i][1],disa[n][i]);
        add(id[n-1][i][1],Start,disa[n][i]);
        add(id[1][i][2],End,disa[1][i]);
        add(End,id[1][i][2],disa[1][i]);
    }
for(int i=1;i<n-1;++i)
for(int j=1;j<m;++j){
            add(id[i][j][1],id[i+1][j][2],disa[i+1][j]);
            add(id[i+1][j][2],id[i][j][1],disa[i+1][j]);
        }
    q.push(Start);dst[Start]=0;
while(!q.empty()){
int from=q.front();vis[from]=0;q.pop();
for(int i=head[from];i;i=edge[i].next){
int to=edge[i].to;
if(dst[to]>dst[from]+edge[i].val){
                dst[to]=dst[from]+edge[i].val;
if(vis[to])    continue;
                vis[to]=1;
                q.push(to);
            }
        }
    }
    printf("%d",dst[End]);
return 0;
}