Problem 2 人偶师(alice.cpp/c/pas)

【题目描述】

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

这题还是高斯消元xor.

不同的是要考虑多解. 

高斯消元多解考虑方法：

Gauss();

dfs(n,1)//把值往回代

如果遇到a[i][i]==0,则分情况dfs.

这样做的好处是O(2^n)  

如果求出所有情况再往回代就是O(n^2*2^n) 

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define MAXN (40+2)
#define MAXM (500+10)
int a[MAXN][MAXN];
int ans[MAXN],tot=MAXN,tot2=0,ans2[MAXN];
int n,m;
/*
void print(int a[MAXN][MAXN],int _n)
{
	for (int i=1;i<=_n;i++)
	{
		for (int j=1;j<=n+1;j++)
			printf("%d ",a[i][j]);
		printf("n");
	}
	printf("===n");
}

void res(int a[MAXN][MAXN])
{
	int tot2=0;
	for (int i=1;i<=n;i++) if (a[i][n+1]) ans2[++tot2]=i;
	if (tot2<tot)
	{
		tot=tot2;
		memcpy(ans,ans2,(tot+1)*sizeof(int));
	}
}
*/
void gauss()
{
	for (int i=1;i<=n;i++)
	{
		if (a[i][i]==0)
			for (int j=i+1;j<=n;j++) if (a[j][i]) {for (int k=1;k<=n+1;k++) swap(a[j][k],a[i][k]);break;}
		if (a[i][i]==0)	continue;
		for (int j=1;j<=n;j++)
			if (a[j][i]&&j!=i)
			{
				for (int k=1;k<=n+1;k++) a[j][k]^=a[i][k];
			}
//		print(a,n);
	}
//	res(a);
}
int uknow[MAXN],uq[MAXN],un=0;
bool b[MAXN]={0};
void dfs(int i,int tot2)
{
	if (tot2>=tot) return;
	if (i==0)
	{
		if (tot2<tot)
		{
			tot=tot2;
			memcpy(ans,ans2,sizeof(tot)*(tot+1));
		}
		return;
	}
	ans2[tot2+1]=i;
	if (a[i][i])
	{
		bool flag=a[i][n+1];
		for (int j=i+1;j<=n;j++) if (a[i][j]&b[j]) flag^=1;
		b[i]=flag;
		dfs(i-1,tot2+flag);
	}
	else
	{
		b[i]=1;
		dfs(i-1,tot2+1);
		b[i]=0;
		dfs(i-1,tot2);
	}

}
int main()
{
	freopen("alice.in","r",stdin);
	freopen("alice.out","w",stdout);
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i][n+1]);
		a[i][n+1]^=1;
		a[i][i]=1;

	}
	for (int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		a[u][v]=a[v][u]=1;
	}
//	print();
//	memcpy(a2,a,sizeof(a));
	gauss();
//	print(a,n);
	for (int i=1;i<=n;i++)
		if (!a[i][i]) uknow[++un]=i;
	dfs(n,0);
//	sort(ans+1,ans+1+tot);
	printf("%dn",tot);
	for (int i=1;i<tot;i++) printf("%d ",ans[i]);
	printf("%dn",ans[tot]);
	return 0;
}

EXTENDED LIGHTS OUT Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 5182   Accepted: 3403 Description Lights Out就是下图的游戏,给你一个5*6的矩阵.  你的目标是把灯全关上.  0表示关,1表示开. Input 第一行为数据组数T. 对于每组数据,输入1个5*6的矩阵. Output 对于每组数据,输出一行 "PUZZLE #m".接下来为还原矩阵. Sample Input 2 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0 Sample Output PUZZLE #1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 PUZZLE #2 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 Source Greater New York 2002

就是Gauss消元的xor版本.

显然若 a1 xor a2 xor a3..=an

             b1 xor b2 xor b3..=bn

        则 (a1 xor b1) xor (a2 xor b2)..=an xor an

满足消元性质

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
const int n=5,m=6;
bool inside(int x){return (x>=0)&&(x<31);}
struct E
{
	int a[31];
	int& operator[](int p){static int t;if (inside(p)) return a[p]; else return t;}
	friend E operator^(E a,E b)
	{
		for (int i=0;i<31;i++) a[i]^=b[i];
		return a;
	}
};
struct M
{
	E a[30];
	E& operator[](int p){return a[p];}
	M()
	{
	//	memset(a,sizeof(a),0);
		for (int i=0;i<30;i++)
			for (int j=0;j<31;j++) a[i][j]=0;
		for(int i=0;i<n*m;i++)
		{
			a[i][i]=a[i][i+6]=a[i][i-6]=1;
			if (i%6) a[i][i-1]=1;
			if (i%6<5) a[i][i+1]=1;

		}
	}
	void gauss()
	{
		int i=0,j=0,n=30,m=31;
		while (i<n&&j<m)
		{
//			print();
			int maxi=i;
			for(int k=i+1;k<n;k++) if (a[k][j]>a[maxi][j]) maxi=k;
			if (a[maxi][j]!=0)
			{
				swap(a[maxi],a[i]);
				for(int k=i+1;k<n;k++)
					if (a[k][j]!=0) a[k]=a[k]^a[i];
			}
			i++;j++;
		}
		for(int i=28;i>=0;i--)
		{
			for(int j=i+1;j<30;j++) if (a[i][j]) {a[i][j]=0;a[i][30]^=a[j][30];	}
		}
		for (int i=0;i<30;i++)
		{
			cout<<a[i][30];
			if (i%6==5) cout<<endl; else cout<<' ';
		}
	}
	void print()
	{
		for (int i=0;i<30;i++)
		{
			for (int j=0;j<31;j++) cout<<a[i][j]<<' ';
			cout<<endl;
		}
		cout<<"--------------------------------------------------n";
		system("pause");
	}


}EM;
int main()
{
//	freopen("poj1222.in","r",stdin);
	int tt;
	cin>>tt;
	for(int t=1;t<=tt;t++)
	{
		EM=M();
		for(int i=0;i<n*m;i++) cin>>EM[i][30];
		cout<<"PUZZLE #"<<t<<endl;
		EM.gauss();


	}
	return 0;
}