BZOJ 4883 [Lydsy2017 年 5 月月赛] 棋盘上的守卫


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4883

题意:在一个 n*m 的棋盘上要放置若干个守卫。对于 n 行来说,每行必须恰好放置一个横向守卫;同理,对于 m 列来说,每列必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的,且每个位置最多只能放置一个守卫,一个守卫不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。


对于每个\(w_{i,j}\),连一条 i-j 的边,然后跑最小生成环套树森林。
怎么跑呢?正常 Kruskal 的过程中,若\(fa_u=fa_v\) 就不能连了,但这里还可以连一条。
所以记录每个连通块是树还是图,若是树,则还可以连过去。就没了。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4883 [Lydsy2017 年 5 月月赛] 棋盘上的守卫


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,