BZOJ 2007 海拔(平面图最小割转对偶图最短路)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

首先注意到，把一个点的海拔定为>1的数是毫无意义的。实际上，可以转化为把这些点的海拔要么定为0，要么定为1.

其次，如果一个点周围的点的海拔没有和它相同的，那么这个点的海拔也是可以优化的，即把这个点变为周围海拔一样的显然能使结果变优。

于是问题就变成了，这个图的海拔为0的联通块和起点连在一起，海拔为1的联通块和终点连在一起。

此即为经典的最小割。

由于此图为平面图，我们可以使用平面图最小割转对偶图最短路优化算法。

因为这是有向图，因此构建对偶图的时候注意边的方向即可。

# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF 1e16
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin...struct Edge{int p, next; LL w;}edge[N*];
struct qnode{
int v; LL c;
qnode(int _v=, LL _c=):v(_v),c(_c){}
bool operator<(const qnode&r)const{return c>r.c;}
};
bool vis[N];
int head[N], cnt=;
LL G1[][], G2[][], G3[][], G4[][], dist[N];
priority_queue<qnode>que;void add_edge(int u, int v, LL w){edge[cnt].p=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;}
void Dijkstra(int n, int start){
mem(vis,false); FOR(i,,n) dist[i]=INF;
dist[start]=; que.push(qnode(start,));
qnode tmp;
while (!que.empty()) {
tmp=que.top(); que.pop();
int u=tmp.v;
if (vis[u]) continue;
vis[u]=true;
for (int i=head[u]; i; i=edge[i].next) {
int v=edge[i].p; LL cost=edge[i].w;
if (!vis[v]&&dist[v]>dist[u]+cost) dist[v]=dist[u]+cost, que.push(qnode(v,dist[v]));
}
}
}
int main ()
{
int n, s, t, x;
scanf("%d",&n); s=; t=n*n+;
FOR(i,,n) FOR(j,,n) scanf("%lld",&G1[i][j]);
FOR(i,,n) FOR(j,,n) scanf("%lld",&G2[i][j]);
FOR(i,,n) FOR(j,,n) scanf("%lld",&G3[i][j]);
FOR(i,,n) FOR(j,,n) scanf("%lld",&G4[i][j]);
FOR(i,,n) FOR(j,,n) {
if (i==) add_edge(s,i*n+j,G1[i][j]), add_edge(i*n+j,s,G3[i][j]);
else if (i==n) add_edge((i-)*n+j,t,G1[i][j]), add_edge(t,(i-)*n+j,G3[i][j]);
else add_edge((i-)*n+j,i*n+j,G1[i][j]), add_edge(i*n+j,(i-)*n+j,G3[i][j]);
}
FOR(i,,n) FOR(j,,n) {
if (j==) add_edge((i-)*n+j+,t,G2[i][j]), add_edge(t,(i-)*n+j+,G4[i][j]);
else if (j==n) add_edge(s,(i-)*n+j,G2[i][j]), add_edge((i-)*n+j,s,G4[i][j]);
else add_edge((i-)*n+j+,(i-)*n+j,G2[i][j]), add_edge((i-)*n+j,(i-)*n+j+,G4[i][j]);
}
Dijkstra(t,s);
printf("%lld\n",dist[t]);
return ;
}