【BZOJ1001】【BJOI2006】狼抓兔子

这道题本来G10跟我说是网络流的

然后我就直接写了个Dinic

于是

于是去搜了一下题解

发现是什么对偶图最短路。。对偶图最短路=最小割=最大流

因为这个图结构固定所以构造对偶图很简单

无标题

大概就是。。原来的每一块变成一个点，原来的边对应新图中的边

然后跑Dijkstra就完了

（虽然比别人写的还是慢点）

// <1001.cpp> - 01/23/16 08:11:02
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
#define T (n-1)<<1,1
#define S (n-1)<<1,0
struct bian{
	int x,y,k;
	bian(int a,int b,int c){x=a,y=b,k=c;}
	bool operator <(bian b) const {return k>b.k;}
	bool operator >(bian b) const {return k<b.k;}
};
int n,m;
int dis[2002][1002];
bool geng[2002][1002];
vector <bian>b[2002][1002];
priority_queue <bian> q;
void make(int x,int y,int mx,int my,int k){
	b[x][y].push_back(bian(mx,my,k));
	b[mx][my].push_back(bian(x,y,k));
}
int main(){
	n=getint(),m=getint();
	if(n==1||m==1){
		if(m==1)swap(n,m);
		int ans=2147483647;
		for(int i=0;i<m-1;i++)ans=min(ans,getint());
		printf("%d",ans);
		return 0;
	}
	for(int i=0;i<n;i++)
		for(int o=0;o<m-1;o++){
			if(!i)make(i<<1,o,T,getint());
			else if(i==n-1)make((i-1)<<1|1,o,S,getint());
			else make(i<<1,o,(i-1)<<1|1,o,getint());
		}
	for(int i=0;i<n-1;i++)
		for(int o=0;o<m;o++){
			if(!o)make(i<<1|1,o,S,getint());
			else if(o==m-1)make(i<<1,o-1,T,getint());
			else make(i<<1|1,o,i<<1,o-1,getint());
		}
	for(int i=0;i<n-1;i++)
		for(int o=0;o<m-1;o++)
			make(i<<1,o,i<<1|1,o,getint());
	for(int i=0;i<(n-1)<<1;i++)
		for(int o=0;o<m-1;o++)dis[i][o]=2147483647;
	dis[(n-1)<<1][1]=2147483647;
	q.push(bian(S,0));
	for(int i=0;i<((n-1)<<1)*(m-1)+2;i++){
		int x=q.top().x,y=q.top().y;q.pop();
		while(geng[x][y]){x=q.top().x,y=q.top().y;q.pop();}
		for(int i=0;i<b[x][y].size();i++){
			int mx=b[x][y][i].x,my=b[x][y][i].y,mk=b[x][y][i].k;
			if(dis[x][y]+mk<dis[mx][my]){
				dis[mx][my]=dis[x][y]+mk;
				q.push(bian(mx,my,dis[mx][my]));
			}
		}
		geng[x][y]=1;
	}
	printf("%d",dis[(n-1)<<1][1]);
	return 0;
}

// <1001.cpp> - 01/23/16 08:11:02

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

#define T (n-1)<<1,1

#define S (n-1)<<1,0

struct bian{

int x,y,k;

bian(int a,int b,int c){x=a,y=b,k=c;}

bool operator <(bian b) const {return k>b.k;}

bool operator >(bian b) const {return k<b.k;}

};

int n,m;

int dis[2002][1002];

bool geng[2002][1002];

vector <bian>b[2002][1002];

priority_queue <bian> q;

void make(int x,int y,int mx,int my,int k){

b[x][y].push_back(bian(mx,my,k));

b[mx][my].push_back(bian(x,y,k));

}

int main(){

n=getint(),m=getint();

if(n==1||m==1){

if(m==1)swap(n,m);

int ans=2147483647;

for(int i=0;i<m-1;i++)ans=min(ans,getint());

printf("%d",ans);

return 0;

}

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

for(int o=0;o<m-1;o++){

if(!i)make(i<<1,o,T,getint());

else if(i==n-1)make((i-1)<<1|1,o,S,getint());

else make(i<<1,o,(i-1)<<1|1,o,getint());

}

for(int i=0;i<n-1;i++)

for(int o=0;o<m;o++){

if(!o)make(i<<1|1,o,S,getint());

else if(o==m-1)make(i<<1,o-1,T,getint());

else make(i<<1|1,o,i<<1,o-1,getint());

}

for(int i=0;i<n-1;i++)

for(int o=0;o<m-1;o++)

make(i<<1,o,i<<1|1,o,getint());

for(int i=0;i<(n-1)<<1;i++)

for(int o=0;o<m-1;o++)dis[i][o]=2147483647;

dis[(n-1)<<1][1]=2147483647;

q.push(bian(S,0));

for(int i=0;i<((n-1)<<1)*(m-1)+2;i++){

int x=q.top().x,y=q.top().y;q.pop();

while(geng[x][y]){x=q.top().x,y=q.top().y;q.pop();}

for(int i=0;i<b[x][y].size();i++){

int mx=b[x][y][i].x,my=b[x][y][i].y,mk=b[x][y][i].k;

if(dis[x][y]+mk<dis[mx][my]){

dis[mx][my]=dis[x][y]+mk;

q.push(bian(mx,my,dis[mx][my]));

}

geng[x][y]=1;

}

printf("%d",dis[(n-1)<<1][1]);

return 0;

}