Source - Click Here
Description
n点m双向边的图，每个点有2个状态：开和关。每次操作改变一个点的状态，以及与其有边直接相连的点的状态。问开启所有点至少需要多少次操作。
Input
第一行2个整数n,m。
第二行n个整数，第i个数表示第i点的状态，0为关，1为开。
第3..m+2行，每行2个整数a,b，表示a和b直接相连，同一条边不会出现多次。
对于30%的数据，1<=n<=10，0<=m<=40
对于60%的数据，1<=n<=30，0<=m<=100
对于100%的数据，1<=n<=40，0<=m<=500
Output
第一行一个整数k表示最少的操作次数，所有数据保证至少有一组可行解。
第二行k个整数，表示操作的点的编号。
Solutions
经典的开关问题，然而高斯消元并不能切掉这道题，最坏还是要$2^N$。
可以这样思考问题，对于一个方案，若从任意点切开分成两个开关状态，两个状态的异或结果是一样的。
因此，若知道任意一个不完整状态，则可以得到另外一部分状态。
这样的话，就可以折半枚举了，只需要知道前$\frac{n}{2}$与后$\frac{n}{2}$的所有可行状态，然后枚举任意一部分的状态，就可以得到另外一部分的状态了。
剩下的，就是暴力搜索加上hash存储方案了。
时间复杂度$O(2^{\frac{n}{2}})$
CODE
CODE - Click Here