bzoj千题计划191：bzoj2337: [HNOI2011]XOR和路径

http://www.lydsy.com/JudgeOnline/problem.php?id=2337

概率不能异或

但根据期望的线性，可以计算出每一位为1的概率，再累积他们的期望

枚举每一位i，现在要计算从1出发第i位异或和为1的概率

令f[u]表示从点u出发，第i为为1的概率

d[u]表示u的度数

枚举与u相连的v

若边权的第i位为1，那么v的第i位为0，f[u]+=(1-f[v])/d[u]

若边权的第i位为0，那么v的第i位为1，f[u]+=f[v]/d[u]

还有一个f[n]=0

将这n个式子，f[i]看做未知数，1/d[i]看做系数

把f[i]都移到左边，1/d 都移到右边

得到n个方程，高斯消元解出来

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 101

#define M 10001

const double eps=1e-;

int n;

int d[N];

int to[M<<],nxt[M<<],front[N],val[M<<],tot;

double a[N][N];

int bit[];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;

}

void gauss()

{

    int r;

    double f;

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

    {

        r=i;

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

            if(abs(a[j][i])>abs(a[r][i])) r=j;

        if(r!=i) swap(a[r],a[i]);

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

        {

            f=a[k][i]/a[i][i];

            for(int j=i;j<=n;++j) a[k][j]-=f*a[i][j];

        }

    }

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

    {

        for(int j=i+;j<n;++j) a[i][n]-=a[j][n]*a[i][j];

        a[i][n]/=a[i][i];

    }

}

int main()

{

    int m;

    read(n); read(m);

    int x,y,w;

    while(m--)

    {

        read(x); read(y); read(w);

        add(x,y,w),d[y]++;

        if(x!=y) add(y,x,w),d[x]++;

    }

    bit[]=;

    for(int i=;i<;++i) bit[i]=bit[i-]<<;

    double ans=;

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

    {

        memset(a,,sizeof(a));

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

        {

            a[j-][j-]=;

            for(int k=front[j];k;k=nxt[k])

                if(val[k]&bit[i])

                {

                    a[j-][to[k]-]+=1.0/d[j];

                    a[j-][n]+=1.0/d[j];

                }

                else a[j-][to[k]-]-=1.0/d[j];

        }

        a[n-][n-]=;

        gauss();

        ans+=a[][n]*bit[i];

    }

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

}