Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

soj.me上的一道很难的题 欢迎大家一起讨论

Posted by ruowu at 2011-09-06 00:53:48
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator