「NOIP模拟赛」人偶师

2014年9月27日1,6161

「题目描述」

n点m双向边的图,每个点有2个状态:开和关。每次操作改变一个点的状态,以及与其有边直接相连的点的状态。问开启所有点至少需要多少次操作。

「输入格式」

第一行2个整数n,m。

第二行n个整数,第i个数表示第i点的状态,0为关,1为开。

第3..m+2行,每行2个整数a,b,表示a和b直接相连,同一条边不会出现多次。

「输出格式」

第一行一个整数k表示最少的操作次数,所有数据保证至少有一组可行解。

第二行k个整数,表示操作的点的编号。

「样例输入」

4 3

1 1 0 0

2 3

1 3

2 4

「样例输出」

3

1 2 3

「数据范围」

对于30%的数据,1<=n<=10,0<=m<=40

对于60%的数据,1<=n<=30,0<=m<=100

对于100%的数据,1<=n<=40,0<=m<=500

善良的学长:虽然解可能不只一个,但是你只要输出任意一个即可得分0.0

题解

dfs直接可得60分。。。

可以分成两半搜索然后hash

我偷懒用了map只有95,卡时也不行

 

说点什么

提醒
avatar
autouke
autouke

黄学长你的折半搜索好像没有过样例啊……