题目大意

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,1)，汇点为 (n,m) (上图中n=4,m=4)。有以下三种类型的道路

• (x, y) <==> (x+1, y)

• (x, y) <==> (x, y+1)

• (x, y) <==> (x+1, y+1)

每条无向边边权＞0，求最小割。

阅读更多……