标签: 最小生成树

1 篇文章

洛谷 – P5994 – [PA2014]Kuglarz
有 $n$ 个杯子排成一行,编号为 $1,2,…,n$,其中某些杯子底下藏有一个小球。
对于任意的 $i\leq j$,题目给定 $c_{i, j}$,表示花费 $c_{ij}$ 元,你就可以知道 $i,i+1,…,j$ 底下藏有球的总数的奇偶性。
求至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?