题目分析
（By duyi）
由于下坡不会增加体力值，而上坡会减小体力值，因此总体来说坡度对我们是不利的，我们要让坡度越少越好。考虑如果整张图都是0，那么大家总的耗费的体力值就是0，由于体力值不为负，此时必然达到最小值。然而本题中强制要求右下角是1，因此我们想到最终构出的图必定是左上角一堆0，右下角一堆1（这样能使相同高度的点最多，要爬的坡最少）。我们要考虑的就是以那一条线作为0和1的分界线。
继续分析问题：这张图原本是连通的，我们要使这张图分为0和1两个部分。每个部分内部不产生代价，两个部分分界处会产生代价。要使代价最小。不难看出，这是一个最小割的模型。
我们知道，最小割=最大流。然而，直接上Dinic算法对于500*500的数据数据是会TLE滴。
由于原图是平面图，所以任意一条边左右都有两个封闭区域，在对偶图中一定有一条边，所以原图中的边一定在对偶图中有一条对应的边
如果我们给原平面图加上源点和汇点，那么原图的最大流就是其对偶图源点到汇点的最短路。
1 #include<bits/stdc++.h> 2 #define INTMAX 2147483647LL 3 #define PII pair<int,int> 4 #define MK make_pair 5 #define re register 6 using namespace std; 7 typedef long long ll; 8 const double Pi=acos(-1.0); 9 const int Inf=0x3f3f3f3f; 10 const int MAXN=505; 11 inline int read(){ 12 re int x=0,f=1,ch=getchar(); 13 while(!isdigit(ch))f=ch=='-'?-1:1,ch=getchar(); 14 while(isdigit(ch))x=x*10+ch-48,ch=getchar(); 15 return x*f; 16 } 17 inline ll readll(){ 18 re ll x=0,f=1,ch=getchar(); 19 while(!isdigit(ch))f=ch=='-'?-1:1,ch=getchar(); 20 while(isdigit(ch))x=x*10+ch-48,ch=getchar(); 21 return x*f; 22 } 23 24 struct Edge{ 25 int to,nxt,cap; 26 }e[MAXN*MAXN<<2]; 27 int head[MAXN*MAXN],cnt; 28 inline void add_edge(int u,int v,int cap){ 29 e[++cnt].to=v;e[cnt].nxt=head[u];e[cnt].cap=cap;head[u]=cnt; 30 } 31 32 int n,S,T; 33 int dis[MAXN*MAXN]; 34 struct RULE{ 35 bool operator()(int &x,int &y)const{ 36 return dis[x]>dis[y]; 37 } 38 }; 39 inline void Dijkstra(){ 40 priority_queue<int,vector<int>,RULE> q; 41 memset(dis,Inf,sizeof(dis)); 42 dis[S]=0;q.push(S); 43 while(!q.empty()){ 44 int x=q.top();q.pop(); 45 for(int i=head[x],y;i;i=e[i].nxt){ 46 y=e[i].to; 47 if(dis[x]+e[i].cap<dis[y]){ 48 dis[y]=dis[x]+e[i].cap; 49 q.push(y); 50 } 51 } 52 } 53 } 54 int main(){ 55 n=read(); 56 S=1;T=n*n+2; 57 for(int i=0,x;i<=n;++i) 58 for(int j=1;j<=n;++j){ 59 x=read(); 60 if(i==0) add_edge(1+j,T,x); 61 else if(i==n) add_edge(S,1+(i-1)*n+j,x); 62 else add_edge(1+i*n+j,1+(i-1)*n+j,x); 63 } 64 for(int i=1,x;i<=n;++i) 65 for(int j=0;j<=n;++j){ 66 x=read(); 67 if(j==0) add_edge(S,1+(i-1)*n+1,x); 68 else if(j==n) add_edge(1+i*n,T,x); 69 else add_edge(1+(i-1)*n+j,1+(i-1)*n+j+1,x); 70 } 71 for(int i=0,x;i<=n;++i){ 72 for(int j=1;j<=n;++j){ 73 x=read(); 74 if(i==0) add_edge(T,1+j,x); 75 else if(i==n) add_edge(1+(i-1)*n+j,S,x); 76 else add_edge(1+(i-1)*n+j,1+i*n+j,x); 77 } 78 } 79 for(int i=1,x;i<=n;++i){ 80 for(int j=0;j<=n;++j){ 81 x=read(); 82 if(j==0) add_edge(1+(i-1)*n+1,S,x); 83 else if(j==n) add_edge(T,1+i*n,x); 84 else add_edge(1+(i-1)*n+j+1,1+(i-1)*n+j,x); 85 } 86 } 87 Dijkstra(); 88 printf("%d ",dis[T]); 89 return 0; 90 }