欢迎来到天天文库
浏览记录
ID:57645684
大小:39.00 KB
页数:7页
时间:2020-08-30
《高斯消元解异或方程组.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、灯Description贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏!牛棚中一共有N(1<=N<=35)盏灯,编号为1到N。这些灯被置于一个非常复杂的网络之中。有M(1<=M<=595)条很神奇的无向边,每条边连接两盏灯。每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。状态
2、改变指的是:当一盏灯是开着的时候,这盏灯被关掉;当一盏灯是关着的时候,这盏灯被打开。问最少要按下多少个开关,才能把所有的灯都给重新打开。数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。Input第一行:两个空格隔开的整数:N和M。第二到第M+1行:每一行有两个由空格隔开的整数,表示两盏灯被一条无向边连接在一起。没有一条边会出现两次。Output第一行:一个单独的整数,表示要把所有的灯都打开时,最少需要按下的开关的数目。SampleInput56121342342553输入细节:一共有五盏灯。灯1、灯4和灯5都连接着灯2和灯3。Sampl
3、eOutput3输出细节:按下在灯1、灯4和灯5上面的开关。SourceUSACONOV09GOLD********************************************************************************* 以ccy的水平,看到这一题,超超超级自然想的是BFS,但是,又超超超容易知道这种想法不是正解。问了下吴老师,他说他们也只想到BFS。然后,ccy在BAIDU上搜了搜,只搜出一条,该条仅此一句话:暴搜过不了,解异或方程组可以…… 额……解异或方程组,ccy听了这么多年,如雷贯耳
4、啊,今天,第一次仔细学习它。 成功搞定,先撒花~~~~~~~~O(∩_∩)O~~~~~~~~~~~~~~~ 一个灯要么不点,要么点一次,所以,灯的次数与状态用0、1就可以表示。 Step1:列方程方程组的格式如下:m[i][j]第i行的第j个未知数的系数;b[i]第i行的值;m[1][1]*x[1]+m[1][2]*x[2]+……+m[1][n]*x[n]=b[1];m[2][1]*x[1]+m[2][2]*x[2]+……+m[2][n]*x[n]=b[2];……m[n][1]*x[1]+m[n][2]*x[2]+……+m[n][
5、n]*x[n]=b[n];对应这题。令b[i]=1,表示编号为i的灯是亮的。m[i][k]=1,表示第k个灯与第i个灯相连,它点不点会影响第i个灯。m[i][k]=0,表示第k个灯与第i个灯未连,它点不点不会影响第i个灯。以这样的规则,我们可以列出n个方程。Step2:解方程这是一个n元一次方程,可以套用高斯消元的方法,只是把原来的加减替换成异或操作。首先建立一个倒三角,使倒三角的第一个未知数x[i][i]的系数尽量保持非0。对于第k行,我们从k行开始到n行,寻找m[i][k]!=0的,使之与k行的方程交换,同时,用第k行与异或k+1~n行m[j
6、][k]!=0的j行,使得k+1~n行的第k列的系数全是0,从上到下,从而形成一个倒三角形。然后从下到上,算得x[n],x[n-1],……,x[1]的值。先看一个求得异或方程组其中一组解得代码:#includeusingnamespacestd;constintmaxn=36;intmap[maxn][maxn];intm[maxn][maxn];intb[maxn];intx[maxn];intn,C;voidinit(){ scanf("%d%d",&n,&C); ints,t; for(inti=1;i
7、<=n;i++) map[i][i]=1; for(inti=1;i<=C;i++) { scanf("%d%d",&s,&t); map[s][t]=1; map[t][s]=1; }}voidmake_bl(){ for(inti=1;i<=n;i++) b[i]=1; for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) m[i][j]=map[i][j];}voidSwap(
8、inti,intj){ for(intu=1;u<=n;u++) swap(m[i][u],m[j][u]);
此文档下载收益归作者所有