如果不考虑数据范围,是最大流板子题,但是$2.5 \times 10^7$级别的点数,显然无法通过。
容易发现原图是平面图,平面图具有良好的性质,其最小割等于其对偶图的最短路,又由最大流-最小割定理,可以将题目转化为最短路问题。
平面图的概念与性质不加赘述,用通俗语言描述就是可以对图进行拓扑变换使得不存在两弧交于顶点之外的点,也就是可以弧互不相交地画在平面上。对偶图则是将平面图的面视作顶点,两面的公共边视作新的边,边权保持一致。
也就是说在对偶图中每个格子是一个顶点,原图中的竖向管道变为横向边,原图中的横向管道变为竖向边。
但是即便转化成了最短路问题,也无法通过此题,那么就需要从此题的特殊性质入手。
我们发现管道向上的容量为无穷,这意味着我们对偶图的横向边有一个方向边权为无穷,在最短路问题中,这等价于不存在边,那么对偶图就是一张分层图,每列为一层,层与层之间只能单调向一侧移动,而每层是一条链,对于一条链内部的最短路,从端点到端点来回递推两遍即可,而层与层之间的转移直接加上横向边边权即可,分析到这里,这题的可通过解法便出现了。
#include <iostream>
using namespace std;
using i64 = long long;
const int N = 5010;
i64 n, m, A, B, Q, x;
int r[N][N], c[N][N];
i64 d[N];
int main() {
cin >> n >> m >> A >> B >> Q >> x;
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= m; j++)
x = c[i][j] = (A * x + B) % Q;
for (int i = 2; i <= n - 1; i++)
for (int j = 1; j < m; j++)
x = r[i][j] = (A * x + B) % Q;
for (int j = 1; j <= m; j++) {
for (int i = 1; i < n; i++) d[i] += c[i][j];
for (int i = 2; i < n; i++) d[i] = min(d[i], d[i - 1] + r[i][j]);
for (int i = n - 2; i; i--) d[i] = min(d[i], d[i + 1] + r[i + 1][j]);
}
i64 res = 1e18;
for (int i = 1; i < n; i++) res = min(res, d[i]);
cout << res << '\n';
return 0;
}
我想问一下,我们发现管道向上的容量为无穷,这意味着我们对偶图的横向边有一个方向边权为无穷。这种有向图的平面图转换为对偶图,对偶图也是有向的么,怎么判断对偶图边权和哪个平面图的边权对应呀