CF1416F - Showing Off

题目大意

有一个网格图 \(A\) ，每个点有一个方向 \(D_{i,j}\) 和一个权值 \(A_{i,j}>0\) ，其中方向指向四联通的某一个点

定义其生成网格图为 \(B\) ，每个点的权值为这个点能够到达的点权值之和

现在给定 \(B\) ，构造一个 \(A\)

分析

每个点一条出边的图是基环内向树，环上的点 \(B_{i,j}\) 相同，树上点权值 \(B_{i,j}>B_{fa_{i,j}}\)

那么对于 \(B\) 中的点，如果能够找到周围一个 \(B_{i',j'}<B_{i,j}\) ，则可以认为 \((i,j)\) 已经确定了方向

否则，周围必须存在点 \(B'_{i,j}\) 与 \(B_{i,j}\) 相同构成环

考虑网格图上不存在奇环，那么可以把环分解为若干极小的二元环，这样的构造是最优的

于是问题降低为二元，变成一个二分图匹配问题，具体的