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

发布于 2017-09-04  112 次阅读


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

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


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

 


一个非常弱的准退役OIER