【寒假作业】【NOIP2010】关押罪犯

“敌人的敌人就是朋友”——毛泽东

恩毛主席领导我们做出了这道题233

首先很容易可以想到的是,按矛盾大小排序,优先分开矛盾大的,不行了就是最大答案

那么用一个并查集维护“朋友关系”

但是这道题只给了“敌人关系”怎么办呢

我们给每个人复制一个人作为敌人,编号为i+n

那么如果要标记两个人为敌人的话,只需要把两个人分别与对方的复制人结为朋友就可以了233

当然这道题也可以用带权并查集做啦233

说点什么

您将是第一位评论人!

提醒
wpDiscuz