OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【ZJOI2009】假期的宿舍

【题目描述】

学校放假了……有些同学回家了,而有些同学则有以前的好朋友来探访,那么住宿就是一个问题。比如A和B都是学校的学生,A要回家,而C来看B,C与A不认识。我们假设每个人只能睡自己直接认识的人的床。那么一个解决方案就是B睡A的床而C睡B的床。而实际情况可能非常复杂,有的人可能认识好多在校学生,在校学生之间也不一定都互相认识。我们已知一共有n个人,并且知道其中每个人是不是本校学生,也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

【输入】

第一行一个数T表示数据组数。接下来T组数据,每组数据第一行一个数n表示涉及到的总人数。接下来一行n个数,第i个数表示第i个人是否是在校学生。接下来一行n个数,第i个数表示第i个人是否回家(0表示不回家,1表示回家,注意如果第i个人不是在校学生,那么这个位置上的数是一个随机的数,你应该在读入以后忽略它)。接下来n行每行n个数,第i行第j个数表示i和j是否认识(1表示认识,0表示不认识,第i行i个的值为0,但是显然自己还是可以睡自己的床),认识的关系是相互的。

【输出】

对于每组数据,如果存在一个方案则输出"^_^"(不含引号),否则输出"T_T"(不含引号)。

【输入样例】

1

3

1 1 0

0 1 0

0 1 1

1 0 0

1 0 0

【输出样例】

^_^

【题解】

容易想到用最大流来判断是否可行。把每个人看做一个节点,如果需要住宿,则由源点向它连边。把每个人对应编号的床看做一个节点,如果这个人住校,则由这张床的节点向汇点连边。如果第i个人可以睡第j张床,则由代表第i个人的节点向代表第j张床的节点连边。最后跑一遍最大流,看答案是否等于需要住宿的人数即可。

【代码】

注意是多组数据,2WA贡献给清空数组……

http://paste.ubuntu.com/11719204/

评论

© OI技术宅 | Powered by LOFTER