【NOIP模拟赛】人偶师

2014年9月27日1,3990

【题目描述】

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,卡时也不行