UVA12125 题解

发布时间 2024-01-13 16:27:39作者: BlNYU

题意

二维平面内有 \(n\) 个冰块,给出冰块的坐标,冰块上的企鹅数和最大跳出次数,企鹅可以在冰块间跳跃,每次跳跃的距离不能超过 \(d\),问哪些冰块可以让所有企鹅跳到上面?

思路

网络流,由于每个冰块有跳出次数限制,所以把一个冰块拆成入点和出点,入点向出点连一条流量为最大跳出次数的边,由源点向每个入点连边,流量为冰块上的企鹅数,对于每个冰块,从出点向其能到的所有冰块的入点连边,流量为 \(+\infty\)。最后依次将每个冰块的入点设为汇点跑最大流,如果最大流为总企鹅数,即代表这个冰块可以让所有企鹅跳到上面。