bzoj1770[Usaco2009 Nov]lights 燈

本文主要是介绍bzoj1770[Usaco2009 Nov]lights 燈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1770

题目大意：

有N 盏灯，电灯间有M 条电线，其中第i 条电线连接了第Ai和Bi盏灯，Ai ̸= Bi，也不会有多条电线重复连接同一组灯。每盏灯上有个开关，开关会改变灯的状态——把不亮的灯点亮，或亮的灯变成不亮。不仅如此，由于电线的作用，按下某盏灯的开关后，和这盏灯直接相连的其他电灯也会随之改变状态。
假设刚开始的时候，所有电灯都是关着的，请问按下哪些灯的开关，才能把所有的灯都点亮？输出按下开关的最少次数，保证解法一定存在。

题解：

高斯消元解异或方程组

算是模版题？具体看注释↓

人生中第一道高斯消元解异或方程组...

于是学了好久。。没脑子的人总要学得慢，毕竟要理解好久啊QwQ

这还是水的呢QwQ都保证有解了...

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 40
//0-不亮/不按/不影响.. 1-xx/xx/xxint n,f[N][N];//f[][]存矩阵 第n+1列就是方程组的解
//在这题里就是1 最终全都要亮
int mymin(int x,int y){return (x<y)?x:y;}
void swop(int &a,int &b){int t=a;a=b;b=t;}
void gauss()
{int i,j,k;for (i=1;i<=n;i++){for (j=i;j<=n&& !f[j][i];j++);//找到一行第i个不为0的 换去第i行去消别人的第i个1if (j>n) continue;if (i!=j)for (k=i;k<=n+1;k++) swop(f[i][k],f[j][k]);//交换for (j=1;j<=n;j++)if (j!=i && f[j][i])//如果这行第i位有1，用第i行消去for (k=1;k<=n+1;k++)f[j][k]^=f[i][k];}
}
int a[N],cnt=0,ans;
void dfs(int now)//求第now个数的解/这题就是求这盏灯是按还是不按
{if (cnt>ans) return;//目前统计的答案比我记录的答案还大 剪枝if (now==0) {ans=mymin(ans,cnt);return;}if (f[now][now])//如果不是自由元{int t=f[now][n+1];for (int i=now+1;i<=n;i++)if (f[now][i]) t^=a[i];//根据前面求到的答案求解a[now]=t;if (t) cnt++;//t=1表示按 0表示不按 dfs(now-1);if (t) cnt--;}else//如果是自由元 就枚举{a[now]=0;dfs(now-1);cnt++;a[now]=1;dfs(now-1);cnt--;}
}
int main()
{//freopen("lights.in","r",stdin);//freopen("lights.out","w",stdout);int m,i,x,y;scanf("%d%d",&n,&m);for (i=1;i<=n;i++) f[i][i]=f[i][n+1]=1;for (i=1;i<=m;i++){scanf("%d%d",&x,&y);f[x][y]=f[y][x]=1;}ans=n;gauss();dfs(n);printf("%d\n",ans);return 0;
}

这篇关于bzoj1770[Usaco2009 Nov]lights 燈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---