本文从WordPress迁移而来, 查看全部WordPress迁移文章
2-sat
题意:有n对夫妻,它们要参加一个活动,数据中每个n行,每行两个时间,表示这对夫妻参加活动在这之间,但是在活动期间有一个典礼,这个典礼的时间是d,这个典礼只能在最开始或者或者最后的d时间内进行,例如总时间是8点到9点,典礼的时间是20分钟,那么典礼只能在2个时间段内进行,分别是8点到8点20分,或者8点40分到9点。你想参加完这n对夫妻的典礼,所以你要给每个夫妻的典礼安排一个时间,使得典礼时间不会冲突,这样你才能全部参加。如果无论怎么安排你都不能参加全部的典礼,那么就输出NO,否则的是输出YES,并且给出任意一种安排方案。不过注意输出的时候,要按照夫妻的顺序,给出它们对应的安排时间(即先输出第1对夫妻的时间,再第2对…..但是具体的时间是任意一组可行解即可)
1 | 每对夫妻的时间就是一对顶点 |
建图部分比较繁琐,因为这题的时间真的比较纠结,处理完这些前期工作,其实就是判断2-sat是否存在可行解,可行的话输出任意一组即可,算是个模板题
1 |
|