BSOJ6202口胡(Bsoj6202 mustache)



然后显然直接跑 MCMF 是会寄掉的。


因为绕着一个环的那个绝对值的最小值相当于最短路,所以我们可以对于每个桌子,连一条边 \((i,(i+1)\bmod n,n)\)(最坏有 \(n\) 个节点会经过这条边)



对于 \(nm\) 个位置,每个位置连每张桌子上对应的位置

每个桌子内部有 \(2n\) 条边。

节点数量是 \(2nm+2\),边数量是 \(nm^2+nm\)。

也许是可以跑过去的。(\(6002\) 个点和 \(30300\) 条边)


A blind mouthwash

Firstly, each point connects edges to the target point, which is obviously a complete matching of bipartite graph.

Then obviously, it will be sent directly to mcmf.

Let’s think about how to let the cost flow model help us calculate the cost “automatically”.

Because the minimum value of the absolute value around a ring is equivalent to the shortest path, we can connect an edge \ ((I, (I + 1) \ bmod n, n) \) (at worst, there are \ (n \) nodes passing through this edge) for each table

Then connect the edges between the tables.


For each position on each table (corresponding to \ nm)

Each table has \ (2n \) edges inside.

The number of nodes is \ (2nm + 2 \), and the number of edges is \ (nm ^ 2 + nm \).

Maybe you can run over. (\ (6002 \) points and \ (30300 \) edges)