【BZOJ1001】狼抓兔子

  原先用Dijkstra写的，由于卡常需要想写spfa，发现spfa慢了很多...

  平面图最小割跑最短路，把面看成点。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010,maxp=2000010;
 
inline void read(int &x)
{
    char ch;
    while ((ch=getchar())<'0' || ch>'9');
    x=ch-'0';
    while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';
}
 
struct Graph
{
    int head[maxp],next[maxp*3],E[maxp*3],D[maxp*3],Ecnt;
    bool In[maxp];
    int Dis[maxp];
    int Que[maxp];
    int top,tail;
     
    inline void Add_Edge(int x,int y,int d)
    {
        next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;D[Ecnt]=d;
        next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;D[Ecnt]=d;
    }
 
    inline void Push_back(int x)
    {
        Que[tail++]=x;
        if (tail>=maxp) tail=0;
        In[x]=true;
    }
 
    inline void Push_front(int x)
    {
        if (--top<0) top=maxp-1;
        Que[top]=x;
        In[x]=true;
    }
 
    inline int Front() {return Que[top];}
    inline void Pop() {In[Front()]=false;if (++top>=maxp) top=0;}
 
    void Spfa(int s,int t)
    {
        memset(Dis,0x7F,sizeof(Dis));
        Push_back(s);Dis[s]=0;
        while (top!=tail)
        {
            int x=Front();Pop();
            for (int i=head[x];i;i=next[i])
                if (Dis[E[i]]>Dis[x]+D[i])
                {
                    Dis[E[i]]=Dis[x]+D[i];
                    if (!In[E[i]])
                        if (Dis[E[i]]<=Dis[Front()]) Push_front(E[i]);
                        else Push_back(E[i]);
                }
        }
        printf("%d\n",Dis[t]);
    }
}G;
 
int n,m,s,t;
 
inline int P(int x,int y,int o) {if (x==n || y==0) return s;if (x==0 || y==m) return t;return (((x-1)*(m-1)+y)<<1)-1+o;}
 
void Init()
{
    read(n),read(m);
    int x;
    s=(n-1)*(m-1)*2+1;t=s+1;
    for (int i=1;i<=n;i++) for (int j=1;j<m;j++) read(x),G.Add_Edge(P(i-1,j,0),P(i,j,1),x);
    for (int i=1;i<n;i++) for (int j=1;j<=m;j++) read(x),G.Add_Edge(P(i,j-1,1),P(i,j,0),x);
    for (int i=1;i<n;i++) for (int j=1;j<m;j++) read(x),G.Add_Edge(P(i,j,0),P(i,j,1),x);
}
 
int main()
{
    Init();
    G.Spfa(s,t);
    return 0;
}