比赛场次 87
比赛名称 20110412pm
比赛状态 已结束比赛成绩
开始时间 2011-04-12 14:30:00
结束时间 2011-04-12 17:30:00
开放分组 全部用户
注释介绍
题目名称 牛棚的灯
输入输出 lights.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 17 简单对比
用户 结果 时间 内存 得分
Gravatar王者自由 AAAAAAAAAAAAAAAAA 0.000 s 0.00 MiB 100
Gravatar苏轼 AAAWAAAWAAAAAAAAA 0.000 s 0.00 MiB 88
GravatarPom AAAAAATTTAAAAAAAA 0.000 s 0.00 MiB 82
Gravatar.Xmz AAAAAAAAATTTTTTTT 0.000 s 0.00 MiB 52
Gravatarwo shi 刘畅 AAAAAAEEEWWWWEEEE 0.000 s 0.00 MiB 35
Gravatarmagic AWWWWWWWWAWWWWWAA 0.000 s 0.00 MiB 23
Gravatarybh AAAWWWWTWWWWWWWWW 0.000 s 0.00 MiB 17

牛棚的灯

★★★   输入文件:lights.in   输出文件:lights.out   简单对比
时间限制:1 s   内存限制:128 MiB

【问题描述】

贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏!

牛棚中一共有N(1 <= N <= 35)盏灯,编号为1到N。这些灯被置于一个非常复杂的网络之中。有M(1 <= M <= 595)条很神奇的无向边,每条边连接两盏灯。

每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是:当一盏灯是开着的时候,这盏灯被关掉;当一盏灯是关着的时候,这盏灯被打开。

问最少要按下多少个开关,才能把所有的灯都给重新打开。

数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。

题目名称:lights

输入格式:

*第一行:两个空格隔开的整数:N和M。

*第二到第M+1行:每一行有两个由空格隔开的整数,表示两盏灯被一条无向边连接在一起。
没有一条边会出现两次。

样例输入(文件 lights.in):

5 6
1 2
1 3
4 2
3 4
2 5
5 3

输入细节:

一共有五盏灯。灯1、灯4和灯5都连接着灯2和灯3。

输出格式:

第一行:一个单独的整数,表示要把所有的灯都打开时,最少需要按下的开关的数目。

样例输出(文件 lights.out):

3

输出细节:

按下在灯1、灯4和灯5上面的开关。