Let's go home
Time Limit: 10000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 624Accepted Submission(s): 195
Problem Description
小时候,乡愁是一枚小小的邮票,我在这头,母亲在那头。
—— 余光中
集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每一对队员,如果队员A留下,则队员B必须回家休息下,或者B留下,A回家。由于今年集训队人数突破往年同期最高记录,管理难度相当大,lcy也不知道自己的决定是否可行,所以这个难题就交给你了,呵呵,好处嘛~,免费**漂流一日。
Input
第一行有两个整数,T和M,1<=T<=1000表示队伍数,1<=M<=5000表示对数。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
Output
可行输出yes,否则输出no,以EOF为结束。
Sample Input
1 2
0 1 2
0 1
1 2
2 4
0 1 2
3 4 5
0 3
0 4
1 3
1 4
Sample Output
Author
威士忌
Source
这个题,很明显可以看到矛盾的对。所以2-sat的模型应该立即显现在脑海中
建图过程也比较好弄
这里我说一个细节问题,很多初学者容易忽视
那就是边的链接方向。
到底是谁指向谁,这个问题,很多初学者容易混淆(比如本人。。)
其实问题的关键是考虑,额。。就用这个题来说吧。
关键是考虑,一个矛盾关系对里面,到底是两个人是能同时出现,还是能同时不出现
这个题里面,队长和队员,是两者可以同时出现的。但是两者却不能同时离开
而后面给的关系里面,是指两个人可以同时走,但是却不能同时都在
于是对于队长和队员,每一个关系对,两种连边的方向是有区别的
队长和队员应该是!a->b,!a->c !b->a,!c->a
每一个关系对里面:a->!b,b->!a
细节容易被忽视。需要特别的注意。
至于2-sat的求解方法,不会的话可以去看那篇OI论文
我的代码:
分享到:
相关推荐
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
杭电组合博弈课件
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
杭州电子科技大学online judge (hdu)第十一卷 2000 - 2099 题目集 doc 格式的,希望大家喜欢!
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
教你小小JAVA爬虫爬到HDU首页(只为学习)-附件资源
HDU 1010-2500解题报告,ACMer可以借鉴一下