bzoj1001/BJOI2006 灰太狼抓到的兔子

1001: [BeiJing2006]狼抓兔子(

id=1001">传送门

)

图论新知识。。没学过。。

平面图最小割等于对偶图的最短路

详见课件：http://wenku.baidu.com/view/8f1fde586edb6f1aff001f7d.html

建议下载 直接在百度看可能有重叠  周冬神犇这个课件的演示很清楚。。

动画效果一看就明确了

代码中的建模方式见图：

/**************************************************************
    Problem: 1001
    User: Lytning
    Language: C++
    Result: 正确
    Time:5212 ms
    Memory:161432 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=3000000+5,M=8000000+5;
struct edge{int u,v,dis; edge *next;}e[M],*point[N],*P=e;
int used[N],d[N],n,m,S=0,T=1;
queue <int> Qe;

inline void add_edge(int a,int b,int dis)
{
    //cout<<"edge added : from "<<a<<" to "<<b<<" dis "<<dis<<endl;
    edge *Q = ++P; ++P;
    P->u = a; P->v = b; P->dis = dis; P->next = point[a]; point[a] = P;
    Q->u = b; Q->v = a; Q->dis = dis; Q->next = point[b]; point[b] = Q;
}

void SPFA(int s)
{
    memset(d,0x7f,sizeof(d));
    memset(used,0,sizeof(used));
    Qe.push(s);
    used[s]=true;
    d[s]=0;
    while(!Qe.empty())
    {
        int x = Qe.front();
        Qe.pop();
        used[x] = false;
        for(edge *j = point[x]; j; j = j->next)
        {
            if(d[x] + j->dis < d[j->v])
            {
                d[j->v] = d[x] + j->dis;
                if(!used[j->v])
                {
                    used[j->v]=true;
                    Qe.push(j->v);
                }
            }
        }
    }
}

inline int number(int x,int y,bool up)//每一个方格以左上角坐标表示
{
    int ret = ((m-1)*(x-1)+y-1)*2+1;
    if(up) ret++;
    return ret+1; // S:0 T:1
}
/*
平面数 : (n-1)*(m-1) *2 

*/
int main()
{
    //freopen("bz1001.in","r",stdin);freopen("bz1001.out","w",stdout);
    cin>>n>>m;
    if(n==1 || m==1)
    {
        int ans=0;
        if(n>m)  m=n;
        for(int z=1; z<m; z++)
        {
            if(z==1)    cin>>ans;
            int t; cin>>t;
            if(t<ans) ans =t;
        }
        cout<<ans<<endl;
    }else{
    //横向
    for(int x=1; x<=n; x++)
    {
        for(int y=1; y<m; y++)
        {
            int t; cin>>t;
            if(x==1)
                add_edge(number(x,y,true),S,t);
            else if (x==n)
                add_edge(number(x-1,y,false),T,t);
            else
                add_edge(number(x,y,true),number(x-1,y,false),t);
        }
    }
    //纵向
    for(int x=1; x<n; x++)
    {
        for(int y=1; y<=m; y++)
        {
            int t; cin>>t;
            if(y==1)
                add_edge(number(x,y,false),T,t);
            else if(y==m)
                add_edge(number(x,y-1,true),S,t);
            else
                add_edge(number(x,y-1,true),number(x,y,false),t);
        }
    }
    //斜
    for(int x=1; x<n; x++)
    {
        for(int y=1; y<m; y++)
        {
            int t; cin>>t;
            add_edge(number(x,y,false),number(x,y,true),t);
        }
    }
    SPFA(S);
    cout<<d[T]<<endl;}
}