BZOJ 2007 海拔

时间:2022-06-19 20:11:50

http://www.lydsy.com/JudgeOnline/problem.php?id=2007

思路:

显然海拔是一片0,另一片1,答案就是01的分界线的流量。

本题中的图是平面图,所以求最小割的时候,可以转换成对偶图最短路,据Gword说:有向边就统一让它顺时针旋转90°,还有,要先将S和T连边,来"劈开"最外面的空白,然后再把S和T分开。

 #include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
int first[],next[],go[],tot,val[];
int dis[],vis[],S,T,n;
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y,int z){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
val[tot]=z;
}
void add(int x,int y,int z){
insert(x,y,z);
}
int id(int x,int y){
if (x==||y==n+) return T;
if (x==n+||y==) return S;
return (x-)*n+y;
}
void dijkstra(){
memset(dis,/,sizeof dis);
priority_queue< pair<int,int> ,vector< pair<int,int> > ,greater<pair<int,int> > > Q;
dis[S]=;
Q.push(make_pair(,S));
while (!Q.empty()){
int now=Q.top().second;Q.pop();
if (vis[now]) continue;
vis[now]=;
for (int i=first[now];i;i=next[i]){
int pur=go[i];
if (dis[pur]>dis[now]+val[i]){
dis[pur]=dis[now]+val[i];
Q.push(make_pair(dis[pur],pur));
}
}
}
}
int main(){
n=read();
S=,T=n*n+;
for (int i=;i<=n+;i++)
for (int j=;j<=n;j++)
add(id(i,j),id(i-,j),read());
for (int i=;i<=n;i++)
for (int j=;j<=n+;j++)
add(id(i,j-),id(i,j),read());
for (int i=;i<=n+;i++)
for (int j=;j<=n;j++)
add(id(i-,j),id(i,j),read());
for (int i=;i<=n;i++)
for (int j=;j<=n+;j++)
add(id(i,j),id(i,j-),read());
dijkstra();
printf("%d\n",dis[T]);
}