bzoj 1001 狼抓兔子 —— 平面图最小割(最短路)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1001

平面图最小割可以转化成最短路问题；

建图时看清楚题目的 input ...

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long ll;

int const xn=2e6+,xm=8e6+;

int n,m,hd[xn],ct,to[xm],nxt[xm],S,T;

ll w[xm],dis[xn],inf=1e17;

bool vis[xn];

struct N{

  int id; ll d;

  N(int i=,ll d=):id(i),d(d) {}

  bool operator < (const N &y) const

  {return d>y.d;}

};

priority_queue<N>q;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void ade(int x,int y,ll z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; w[ct]=z;}

void add(int x,int y,ll z){ade(x,y,z); ade(y,x,z);}

int id(int x,int y,int z){return ((x-)*(m-)+(y-))*++z;}//格子(x,y) 0\1

void dij()

{

  for(int i=S;i<=T;i++)dis[i]=inf;

  dis[S]=; q.push(N(S,));

  while(q.size())

    {

      int x=q.top().id; q.pop();

      if(vis[x])continue; vis[x]=;

      for(int i=hd[x],u;i;i=nxt[i])

      if(dis[u=to[i]]>dis[x]+w[i])

        dis[u]=dis[x]+w[i],q.push(N(u,dis[u]));

    }

}

int main()

{

  n=rd(); m=rd(); S=; T=id(n-,m-,)+; ll x;

  if(n<=||m<=)

    {

      if(n<=||m<=||(n==&&m==)){puts(""); return ;}

      ll mn=inf;

      if(n==) for(int i=;i<m;i++)x=rd(),mn=min(x,mn);

      else if(m==) for(int i=;i<n;i++)x=rd(),mn=min(x,mn);

      printf("%lld\n",mn); return ;

    }

  for(int j=;j<m;j++)x=rd(),add(T,id(,j,),x);

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

    for(int j=;j<m;j++)x=rd(),add(id(i-,j,),id(i,j,),x);

  for(int j=;j<m;j++)x=rd(),add(id(n-,j,),S,x);

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

    {

      x=rd(); add(S,id(i,,),x);

      for(int j=;j<m;j++)x=rd(),add(id(i,j-,),id(i,j,),x);

      x=rd(); add(id(i,m-,),T,x);

    }

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

    for(int j=;j<m;j++)x=rd(),add(id(i,j,),id(i,j,),x);

  dij();

  printf("%lld\n",dis[T]);

  return ;

}