【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=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

struct Edge{

    int next,to,val;

}edge[];

int head[],num;

inline void add(int from,int to,int val){

    edge[++num]=(Edge){head[from],to,val};

    head[from]=num;

}

int disa[][],disb[][],id[][][];

int ID,Start,End;

bool vis[];

int dst[];

int main(){

    memset(dst,/,sizeof(dst));

    int n=read(),m=read();

    End=n*m+;

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

        for(int j=;j<m;++j)

            disa[i][j]=read();

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

        for(int j=;j<=m;++j)

            disb[i][j]=read();

    if(n==){

        int a=0x7fffffff;

        for(int i=;i<m;++i)    a=min(a,disa[][i]);

        printf("%d",a);

        return ;

    }

    if(m==){

        int a=0x7fffffff;

        for(int i=;i<n;++i)    a=min(a,disb[i][]);

        printf("%d",a);

        return ;

    }

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

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

            int x=read();

            id[i][j][]=++ID;

            id[i][j][]=++ID;

            add(id[i][j][],id[i][j][],x);

            add(id[i][j][],id[i][j][],x);

        }

    for(int i=;i<n;++i){

        add(Start,id[i][][],disb[i][]);

        add(id[i][][],Start,disb[i][]);

        add(id[i][m-][],End,disb[i][m]);

        add(End,id[i][m-][],disb[i][m]);

    }

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

        for(int j=;j<m-;++j){

            add(id[i][j][],id[i][j+][],disb[i][j+]);

            add(id[i][j+][],id[i][j][],disb[i][j+]);

        }

    for(int i=;i<m;++i){

        add(Start,id[n-][i][],disa[n][i]);

        add(id[n-][i][],Start,disa[n][i]);

        add(id[][i][],End,disa[][i]);

        add(End,id[][i][],disa[][i]);

    }

    for(int i=;i<n-;++i)

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

            add(id[i][j][],id[i+][j][],disa[i+][j]);

            add(id[i+][j][],id[i][j][],disa[i+][j]);

        }

    q.push(Start);dst[Start]=;

    while(!q.empty()){

        int from=q.front();vis[from]=;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]=;

                q.push(to);

            }

        }

    }

    printf("%d",dst[End]);

    return ;

}