[bzoj1001] [BeiJing2006]狼抓兔子

思路

平面圖最小割轉對偶圖最短路。

（注意：要特判n或m等于1的情況，bzoj上有一組m=1的資料。）

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 2000020
#define maxm 6000060
using namespace std;
int tot,n,m,s,t,la[maxn],d[maxn];
bool inq[maxn];queue<int>q;
struct edge{int v,ne,c;}e[maxm];
inline void add(int u,int v,int c){e[tot].v=v,e[tot].ne=la[u],e[tot].c=c,la[u]=tot++;}
inline void get(int &x){
	char c=getchar();bool p=0;
	while((c<'0'||c>'9')&&c!='-')c=getchar();
	if(c=='-')p=1,c=getchar();x=c-'0',c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	if(p)x=-x;
}
inline int id(int x,int y,int p){
	return ((x-1)*(m-1)+y)*2+p;
}
void init(){
    memset(la,-1,sizeof(la));
	tot=0;s=maxn-1,t=maxn-2;
	get(n),get(m);
	for(int i=1;i<m;++i){
		int c;get(c);
		if(n==1){
			add(s,t,c),add(t,s,c);
			continue;
		}
		add(s,id(1,i,0),c),add(id(1,i,0),s,c);
	}
	for(int i=2;i<n;++i)
	for(int j=1;j<m;++j){
		int c;get(c);
		add(id(i-1,j,1),id(i,j,0),c),add(id(i,j,0),id(i-1,j,1),c);
	}
	for(int i=1;i<m;++i){
		int c;get(c);
		add(id(n-1,i,1),t,c),add(t,id(n-1,i,1),c);
	}
	for(int i=1;i<n;++i){
		for(int j=1;j<=m;++j){
			int c;get(c);
			if(j==1&&j==m){
				add(s,t,c),add(t,s,c);
				continue;
			}
			if(j==1){
				add(t,id(i,j,1),c),add(id(i,j,1),t,c);
				continue;
			}
			if(j==m){
				add(id(i,j-1,0),s,c),add(s,id(i,j-1,0),c);
				continue;
			}
			add(id(i,j-1,0),id(i,j,1),c);add(id(i,j,1),id(i,j-1,0),c);
		}
	}
	for(int i=1;i<n;++i)
	for(int j=1;j<m;++j){
		int c;get(c);
		add(id(i,j,0),id(i,j,1),c),add(id(i,j,1),id(i,j,0),c);
	}
}
void spfa(){
	memset(inq,0,sizeof(inq));
	memset(d,127/2,sizeof(d));
	d[s]=0;inq[s]=1,q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=la[u];~i;i=e[i].ne){
			int v=e[i].v,c=e[i].c;
			if(d[u]+c<d[v]){
				d[v]=d[u]+c;
				if(!inq[v])
				inq[v]=1,q.push(v);
			}
		}
		inq[u]=0;
	}
}
void solve(){
	spfa();
	printf("%d\n",d[t]);
}
int main(){
	init();
	solve();
	return 0;
}