[文章目录]
Description
YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。 小Z作为该市的市长，他根据统计信息得到了每天上班高峰期间YT市每条道路两个方向的人流量，即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值，YT市市民认为爬坡是一件非常累的事情，每向上爬h的高度，就需要消耗h的体力。如果是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为h(注意h可能是负数)，那么一个人经过这段路所消耗的体力是max{0, h}（这里max{a, b}表示取a, b两个值中的较大值）。 小Z还测量得到这个城市西北角的交叉路口海拔为0，东南角的交叉路口海拔为1(如上图所示)，但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡所消耗的总体力和的最小值。
平面高度是单调的，那么就是将平面变成01两部分，计算代价，网络流最小割。发现是平面图，平面图转对偶图求最短路即可，注意同方向的两边边权不同。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,s,t;
int head[251000],to[1100000],nxt[1100000],f[1100000],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
ll dis[251000];
bool vis[251000];
queue<int>q;
void spfa()
{
memset(dis,0x3f,sizeof dis);
q.push(s); dis[s]=0; int x; vis[s]=1;
while(!q.empty())
{
x=q.front(); q.pop(); vis[x]=0;
for(int i=head[x];i;i=nxt[i])
if(dis[to[i]]>dis[x]+f[i])
{
dis[to[i]]=dis[x]+f[i];
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
}
int main()
{
scanf("%d",&n); s=n*n+1; t=n*n+2; int x,y,z;
for(int i=0;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&z);
x=(i==n)?s:i*n+j;
y=(i==0)?t:(i-1)*n+j;
add(x,y,z);
}
for(int i=1;i<=n;++i)
for(int j=0;j<=n;++j)
{
scanf("%d",&z);
x=(j==0)?s:(i-1)*n+j;
y=(j==n)?t:(i-1)*n+j+1;
add(x,y,z);
}
for(int i=0;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&z);
x=(i==0)?t:(i-1)*n+j;
y=(i==n)?s:i*n+j;
add(x,y,z);
}
for(int i=1;i<=n;++i)
for(int j=0;j<=n;++j)
{
scanf("%d",&z);
x=(j==n)?t:(i-1)*n+j+1;
y=(j==0)?s:(i-1)*n+j;
add(x,y,z);
}
spfa();
printf("%lld",dis[t]);
return 0;
}