bzoj2337 XOR和路径——高斯消元

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2337

异或就一位一位考虑；

x为到n的概率，解方程组即可；

考虑了n就各种蜜汁错误，所以索性不管n了，这样的题好像不管n比较方便。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int const M=;

int n,m,d[],head[],ct;

double a[][],ans,x[];

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[M<<];

void add(int x,int y,int z)

{

    edge[++ct]=N(y,head[x],z);head[x]=ct;

    d[x]++;

}

void gauss()

{

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

    {

        int k=i;

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

            if(fabs(a[j][i])>fabs(a[k][i]))k=j;

        if(k!=i)

            for(int j=i;j<=n+;j++)swap(a[k][j],a[i][j]);

        for(int j=n+;j>=i;j--)a[i][j]/=a[i][i];

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

            for(int l=n+;l>=i;l--)//倒序！！！

                a[j][l]-=a[j][i]*a[i][l];

    }

    for(int i=n-;i;i--)

    {

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

            a[i][n+]-=a[i][j]*x[j];

        x[i]=a[i][n+];

    }

}

void work(int nw)

{

    memset(a,,sizeof a);

    memset(x,,sizeof x);

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

    {

        for(int j=head[i];j;j=edge[j].next)

        {

            int to=edge[j].to;

            int w=edge[j].w;

            if(w&nw)a[i][to]-=1.0/d[i],a[i][n+]-=1.0/d[i];

            else a[i][to]+=1.0/d[i];

        }

        a[i][i]-=;

    }

    gauss();

    ans+=x[]*nw;

}

int main()

{

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

    for(int i=,x,y,z;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

        if(x!=y)add(y,x,z);

    }

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

        work(<<i);

    printf("%.3lf",ans);

    return ;

}