Gravatar
hsl_beat
积分:186
提交:22 / 31


最小割必刷题!



首先我们先把棋盘看作二分图黑白染色,比如我们可以把横纵坐标加起来为奇数的看作黑,偶数看作白。



考虑到一个黑色节点只会对它四周的节点产生影响,不难想到我们直接把把源点往所有黑点连边权为这个点在棋盘上的数的边,白点同理,只是往汇点连边,然后相邻的方格之间连无穷大的边,这样这些边就不会被算在割边中。



那我们对于舍弃一个点,就是把这个点往源点或汇点的边割掉,dinic跑最小割即可。(ISAP不会写QAQ)



题目734  [网络流24题] 方格取数问题 AAAAAAAAAAA      4      1 条 评论
2025-09-25 20:49:45