| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
soj.me上的一道很难的题 欢迎大家一起讨论http://soj.me/2508
Description
蒙古的水轮法王对水国发起了偷袭,并且占领了水国的一些领土。水浩做为水国的国王,想要进行抵抗运动来收复失地。水浩首先要选择一些人,这些人被分成两组:间谍和后勤组。间谍在被占领的领土上活动,后勤组在没有被占领的领土上活动。
但是有一个问题——两个组的划分必须满足以下的限制:
1. 后勤组的每一对人必须相互认识——这样整个组工作才更有效率;
2. 间谍必须互相不认识;
3. 这两组都不能为空。
水浩想要知道一共有多少种划分方法。
Input
第一行整数N(),表示人数,以下n行分别描述每个人的信息。
第i行先是一个数ki,表示i这个人认识的人数,之后ki个数,分别表示他认识的人。
每个人不会认识他自己,并且认识是对称的,i认识j那么j也认识i。
Output
数据一个数,即划分方案数。
Sample Input
4
2 2 3
2 1 3
3 1 2 4
1 3Sample Output
3Hint
样例中的方案如下:
1 4
2 4
4
为间谍
------------------------------------------------------------------------------------------------------
我觉得这题目的关键点有以下2个:
1. 如何高效而快速地找出图中的那个最大团;如果能找出,问题就能解决一大半;
2. 其次,对于那种没有顶点数>=3的最大团的图,在该问题背景下,也就演化为树的结构,这样再找出其化分数。
我对于第一个关键问题的思路,陷入僵局,现正努力试图用分治的方法给予解答,但是,这样做能不能快速找出该问题下的最大团,尚疑虑其证据足否?
欢迎大家一起探讨,更希望大牛们一展身手!~~
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator