[BZOJ] 1001: [BeiJing2006]狼抓兔子

ST平面图最小割=ST平面图对偶图最短路

 

建图按边割开的边的边权建，特别地将S到T分成两个平面，设为SS和TT。

 

有一种情况是n=1或m=1，需要特殊处理。

注意到这种情况一定是一条链，边权为正，所以答案就是最远点了。

 

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

using namespace std;

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}

const int MAXN=3000000;
const int M=3000000;

struct Edge{
  int next,to,w;
}e[M<<1];
int ecnt,head[MAXN];
inline void adds(int x,int y,int w){
  e[++ecnt].next = head[x];
  e[ecnt].to = y;
  e[ecnt].w = w;
  head[x] = ecnt;
}
inline void add(int x,int y,int w){
  adds(x,y,w);adds(y,x,w);
}
struct Node{
  int id,w;
  Node(int x=0,int y=0){id=x;w=y;}
  bool operator < (const Node &rhs) const {
    return w>rhs.w;
  }
}top;
priority_queue<Node> Q;
int dis[MAXN],vis[MAXN];
void dij(int s){
  memset(dis,0x3f,sizeof(dis));
  Q.push(Node(s,0));dis[s]=0;
  while(!Q.empty()){
    top=Q.top();Q.pop();
    int mnid=top.id,mn=top.w;
    if(vis[mnid]) continue;
    if(mn!=dis[mnid])continue;vis[mnid]=1;
    for(int i=head[mnid];i;i=e[i].next){
      int v=e[i].to;
      if(dis[v]>dis[mnid]+e[i].w){
        dis[v]=dis[mnid]+e[i].w;
        Q.push(Node(v,dis[v]));
      }
    }
  }
}

int n,m,S,T;
#define id(x,y) ((((x)-1)*(m-1<<1))+(y))
int main(){
    n=rd();m=rd();
    S=n*m*2+1;T=n*m*2+2;
    int x;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m-1;j++){
        x=rd();
        if(i==1){add(id(1,j<<1),T,x);continue;}
        if(i==n){add(id(n-1,(j<<1)-1),S,x);continue;}
        add(id(i-1,(j<<1)-1),id(i,j<<1),x);
      }
    }
    for(int i=1;i<=n-1;i++){
      for(int j=1;j<=m;j++){
        x=rd();
        if(j==1){add(id(i,(j<<1)-1),S,x);continue;}
        if(j==m){add(id(i,j-1<<1),T,x);continue;}
        add(id(i,(j-1)<<1),id(i,(j<<1)-1),x);
      }
    }
    for(int i=1;i<=n-1;i++){
      for(int j=1;j<=m-1;j++){
        x=rd();
        add(id(i,(j<<1)-1),id(i,j<<1),x);
      }
    }
    dij(S);
    if(n!=1&&m!=1) return cout<<dis[T],0;
    int ans=0;
    for(int i=1;i<=n*m;i++) 
      if(dis[i]!=0x3f3f3f3f)
        ans=max(ans,dis[i]);
    cout<<ans;
    return 0;
}