高斯消元解异或方程组.doc

《高斯消元解异或方程组.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]);