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 ;
}