题解：P10698 [SNCPC2024] 最大流

Cadmus · 2026-01-18 01:48:21 · 题解

考虑 LGV 引理，由于 LGV 的条件是点不交，将边拆成点，每个点所有入边向所有出边连边。

建 k 个虚点，向 1 的所有出边连边。给每条边赋一个随机权值 w_{i,j}，设 A_{i,j} 表示第 j 个虚点到第 i 条边的路径权值乘积和。设 x 的入边集合即为 S，出边集合为 T，对于所有 i\in T，A_i=\sum w_{j,i}A_j。x 的答案为 S 中 i 的 A_i 组成的矩阵的秩。

但是这样如果出度入度都很大就会爆炸。考虑将 S 中的向量求出一组线性基 B，那么每个 A_j 都可以表示为若干个 B_x 的和，独立的随机数的和仍然是随机数，因此直接令 A_i=\sum w_{j,i}B_j 即可。

实现时维护每个点入边向量的线性基即可。

复杂度 O((n+m)k^2)。