本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分图 最大匹配 输出字典序最大的匹配
题意:每个学生说出他的排名的区间[a,b](区间范围在[1,100000]),但是学生之间的话可能相互矛盾,即有人说谎,选出最多的学生,使他们说的话没有矛盾,如果有多种情况,选出的学生编号要求字典序最大
虽然排名的区间很大,但是算一下复杂度是没有超过限制的。构图,X部为学生编号,Y部为排名,对于u这个学生,他在排名在[a,b],就连边 for(int i = a; i <= b; i++) u -> i。然后求一次最大匹配,就能求出最多多少学生可以共存。另外要求字典序最大,思考匈牙利算法的运行过程,在枚举点做增广路的过程中,只要从编号大的顶点开始枚举,就可以先满足前面的顶点,这样的匹配结果能保证字典序最大,将能匹配的点保存下来,最好排序后输出即可
1 |
|