BZOJ2007/LG2046 「NOI2010」海拔 平面图最小割转对偶图最短路

时间:2022-09-13 07:05:51

问题描述

BZOJ2007

LG2046


题解

发现左上角海拔为 \(0\) ,右上角海拔为 \(1\) 。

上坡要付出代价,下坡没有收益,所以有坡度的路越少越好。

所以海拔为 \(1\) 的点,和海拔为 \(0\) 的点,一定能够在这个网格图中由一条连续的线划分为两个集合。

将一个图中的所有结点划分为两个集合,显然为最小割模型。

又发现是网格图,所以平面图最小割转化为对偶图最短路。


\(\mathrm{Code}\)

不删调试见祖宗

#include<bits/stdc++.h>
using namespace std; const int maxn=500*500+3; int n,S,T;
int Head[maxn],to[maxn*5],Next[maxn*5],w[maxn*5],tot=1;
int fr[maxn*5]; void add(int x,int y,int z){
fr[++tot]=y,to[tot]=x,Next[tot]=Head[y],Head[y]=tot,w[tot]=z;
} int id(int x,int y){
return (x-1)*n+y;
} void Init(void){
scanf("%d",&n);
} void WestToEast(void){
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
add(id(1,i),S,x);
}
for(int i=2;i<=n;i++){
for(int j=1,x;j<=n;j++){
scanf("%d",&x);
add(id(i,j),id(i-1,j),x);
}
}
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
add(T,id(n,i),x);
}
} void NorthToSouth(void){
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
add(T,id(i,1),x);
for(int j=2;j<=n;j++){
scanf("%d",&x);
add(id(i,j-1),id(i,j),x);
}
scanf("%d",&x);
add(id(i,n),S,x);
}
} void EastToWest(void){
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
add(S,id(1,i),x);
}
for(int i=2;i<=n;i++){
for(int j=1,x;j<=n;j++){
scanf("%d",&x);
add(id(i-1,j),id(i,j),x);
}
}
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
add(id(n,i),T,x);
}
} //n lines
//n+1 every-line void SouthToNorth(void){
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
add(id(i,1),T,x);
for(int j=2;j<=n;j++){
scanf("%d",&x);
add(id(i,j),id(i,j-1),x);
}
scanf("%d",&x);
add(S,id(i,n),x);
}
} void debug(){
printf("\n### S = %d\n",S);
printf("### T = %d\n\n",T);
for(int i=2;i<=tot;i++){
printf("*** From %d To %d , val = %d\n",fr[i],to[i],w[i]);
}
} void Graph_build(void){
S=n*n+1,T=S+1;
WestToEast();
NorthToSouth();
EastToWest();
SouthToNorth();
} int dis[maxn];
bool vis[maxn];
#define pii(x,y) make_pair(x,y) void dijkstra(void){
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> >q;
q.push(pii(0,S));dis[S]=0;
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis[x]) continue;vis[x]=1;
if(x==T) return;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(dis[y]>dis[x]+w[i]){
dis[y]=dis[x]+w[i];
q.push(pii(-dis[y],y));
}
}
}
} void Work(void){
Graph_build();
#ifndef ONLINE_JUDGE
// debug();
#endif
dijkstra();
printf("%d\n",dis[T]);
} int main(){
#ifndef ONLINE_JUDEG
// freopen("hzlbn.in","r",stdin);
#endif
Init();
Work();
return 0;
}