[haoi2005]奇特的图案

Grade Open Time Friday, 19 September 2014, 10:04 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:04 am
Allow late Yes Close Time Friday, 26 September 2014, 10:04 am
Input file t3.in Output file t3.out

问题描述

   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,可以使所有的灯都亮。