【题目描述】
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
题解
高斯消元解异或方程组。我怎么这么弱……
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> using namespace std; int n,m,a[50][50]; int ans,ct,s[50],as[50]; void init() { scanf("%d%d",&n,&m); int i,x,y; for(i=1;i<=n;i++) {scanf("%d",&x); a[i][i]=1; a[i][n+1]=x^1;} for(i=1;i<=m;i++) {scanf("%d%d",&x,&y); a[x][y]=a[y][x]=1; } } void gaos() { int i,j,k; for(i=1;i<=n;i++) {j=i; while(j<=n&&a[j][i]==0) j++; if(j>n) continue; if(j!=i) {for(k=1;k<=n+1;k++) swap(a[i][k],a[j][k]); } for(j=1;j<=n;j++) {if(a[j][i]==1&&i!=j) {for(k=1;k<=n+1;k++) a[j][k]^=a[i][k];} } } } void dfs(int x) { if(ct>=ans) return ; int i,num; if(x==0) {if(ct<ans) {ans=ct; for(i=1;i<=n;i++) as[i]=s[i]; } return ; } if(a[x][x]) {num=a[x][n+1]; for(i=x+1;i<=n;i++) {if(a[x][i]) num^=s[i];} s[x]=num; if(num==1) ct++; dfs(x-1); if(num==1) ct--; } else {s[x]=0; dfs(x-1); s[x]=1; ct++; dfs(x-1); ct--; } } int main() { freopen("alice.in","r",stdin); freopen("alice.out","w",stdout); init(); gaos(); ans=1<<30; dfs(n); printf("%d\n",ans); int i; for(i=1;i<=n;i++) if(as[i]) printf("%d ",i); return 0; }