为什么额外加上最小的点权一定正确?

P2916 [USACO08NOV] Cheering up the Cow G

没有错啊,每条边都跑两次,边权变为原边*2+两个顶点点权,这种算法只少算了出发点,因为只有它没有被从其他地方到过而加上其点权。最后我们就要加上这个点权,肯定取最小的啊
by maoyinuo @ 2021-07-09 08:33:58


|