题目大意

YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为$n\times n$个区域。YT城市中包括$(n+1)\times (n+1)$个交叉路口和$2\times n\times(n+1)$条双向道路，每条双向 道路连接主干道上两个相邻的交叉路口。

小Z作为市长统计到了每条道路的人流量$w_i$，然而每个点都有一定的海拔$h_i(0\leqslant h_i\leqslant 1)$，那么经过一条道路需要耗费的体力值为$w_i\times max(0,h_{终点}-h_{起点})$

已知起点为右上角，海拔为0，终点为左下角，海拔为1，求最少耗费多少体力值。

顺便给出样例的图

数据范围

$1\leqslant n\leqslant 500,0\leqslant 流量\leqslant 1,000,000$且所有流量均为整数。

题解

找出图中海拔最高的点，如果它不是起点，那么总是可以把它调小使得结果更优。那么最高点最后就必然为终点。同理可知最低点必然为起点。那么图中有没有可能存在小数使得结果更优呢？同样可以把小数向上或向下调整到1或0使得代价不增。

所有海拔为0的点必然互相连通。为什么呢？显然，四面连接1的0如果使它取1必然使结果更优。同理可推海拔为1的点。

把每边人流量设为这条边的流量，求出割，分成海拔分别为0和1的两块。这时耗费体力值最少。

这题的做法和【bzoj1001】狼抓兔子一样的，对偶图最小割等于新图最短路。只不过这题的边是单向边，那题是双向边。

求出新图，跑一边最短路就可以了。

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
using namespace std;

int n,cnt,et,s,t,x;
struct edge{int to,next,c;}e[2005000];
int d[250500],last[250500],flag[250500];
inline void addedge(int u,int v,int c){e[++et].to=v;e[et].c=c;e[et].next=last[u];last[u]=et;}

inline void spfa(){
    queue <int> q;memset(d,inf,sizeof(d));
    d[s]=0;q.push(s);flag[s]=1;
    while (!q.empty()){
        int h=q.front();q.pop();flag[h]=0;
        goedge(i,h)
            if (d[h]+e[i].c<d[e[i].to]){
                d[e[i].to]=d[h]+e[i].c;
                if (!flag[e[i].to]){q.push(e[i].to);flag[e[i].to]=1;}
            }
    }
}

int main(){
    scanf("%d",&n);s=0;t=n*n+1;
    For(i,1,n+1) For(j,1,n){
        int c;scanf("%d",&c);++cnt;
        int u=cnt,v=cnt-n;
        if (i==1) v=t;if (i==n+1) u=s;
        addedge(u,v,c);
    }cnt=0;
    For(i,1,n) For(j,1,n+1){
        int c;scanf("%d",&c);if (j!=1) ++cnt;
        int u=cnt,v=cnt+1;
        if (j==1) u=s;if (j==n+1) v=t;
        addedge(u,v,c);
    }cnt=0;
    For(i,1,n+1) For(j,1,n){
        int c;scanf("%d",&c);++cnt;
        int u=cnt-n,v=cnt;
        if (i==1) u=t;if (i==n+1) v=s;
        addedge(u,v,c);
    }cnt=0;
    For(i,1,n) For(j,1,n+1){
        int c;scanf("%d",&c);if (j!=1) ++cnt;
        int u=cnt+1,v=cnt;
        if (j==1) v=s;if (j==n+1) u=t;
        addedge(u,v,c);
    }cnt=0;
    spfa();
    printf("%d\n",d[t]);
    return 0;
}