USACO2009NOV Gold 灯

wjh15101051's space

卧薪尝胆，厚积薄发。

USACO2009NOV Gold 灯

Date: Sat Jun 30 21:06:06 CST 2018

In Category: NoCategory

Description：

一个图上改变一个灯会影响所有与它相邻的灯的开关状态，求最小操作次数使得所有的灯都被点亮。

$1\le N\le 35$

Solution：

每个灯操作两次不受影响， $\%2$ 相当于异或，故异或有线性性质，列出异或方程组用高斯消元解方程。最后 $dfs$ 枚举所有自由元的取值求最小即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 36

typedef long long ll;

ll g[MAXN];

int bit(ll a,int pos)

{

	return ((a >> (pos - 1)) & 1);

}

void gauss()

{

	for(int i = 1;i <= n;++i)

	{

		bool found = true;

		for(int j = i;j <= n;++j)

		{

			if(bit(g[j],i))

			{

				swap(g[i],g[j]);

				found = true;

				break;

			}

		}

		if(!found)continue;

		for(int j = i + 1;j <= n;++j)

		{

			if(bit(g[j],i))

			{

				g[j] ^= g[i];

			}

		}

	}

	return;

}

int res[MAXN];

int ans = 0x3f3f3f3f;

void dfs(int cur,int tot)

{

	if(tot > ans)return;

	if(cur == 0)

	{

		ans = min(ans,tot);

		return;

	}

	if(bit(g[cur],cur))

	{

		res[cur] = bit(g[cur],n + 1);

		for(int i = cur + 1;i <= n;++i)res[cur] ^= res[i] & bit(g[cur],i);

		if(res[cur] == 0)dfs(cur - 1,tot);

		else dfs(cur - 1,tot + 1);

	}

	else

	{

		res[cur] = 0;dfs(cur - 1,tot);

		res[cur] = 1;dfs(cur - 1,tot + 1);

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		g[a] |= (1ll << (b - 1));

		g[b] |= (1ll << (a - 1));

	}

	for(int i = 1;i <= n;++i)

	{

		g[i] |= (1ll << (i - 1));

		g[i] |= (1ll << (n + 1 - 1));

	}

	gauss();

	dfs(n,0);

	cout << ans << endl;

	return 0;

}

In tag: 数学-高斯消元

wjh15101051