OI题库

【问题描述】

   X城将举办一次民俗文化节，其活动的标志是设在主会场的奇特图案。该图案是由若干个三角形组成的，且每个三角形都至少有一条边与其它三角形共边。该图案共有N个顶点，每个顶点上有一个彩灯，白天各顶点上彩灯的状态是随机的，有的灯亮，有的灯不亮，但一到晚上20：00，所有顶点上的彩灯必须瞬间全亮。

  控制中心设有N个控制开关，第1个开关可以改变第1个顶点以及与它相邻的顶点彩灯的状态(即：亮->不亮， 不亮->亮)。请你为控制中心设计一个按下开关个数最少的方案，它能根据白天各个顶点上彩灯的状态，瞬间使所有顶点上的彩灯都亮。

【输入文件】

t3.in

第1行： N (顶点个数 4<=N<=1000 )
第2~N+I行： Ki J1 J2… (第1个顶点的状态及相邻的顶点编号)
 

【输出文件】

t3.out

M(按下开关的个数)

【约定】

(1) Ki=1表示第I个顶点上彩灯亮，Ki=0表示第I个顶点上彩灯不亮 i=1,2…,N
 

【样例输入】

t3.in

5
1 3 4 5
0 3 4
0 1 2 4
1 1 2 3 5
0 1 4

 

【样例输出】

t3.out

2

注：按下开关3和5，可以使所有的灯都亮。