$f[x]=\frac{\sum f[y]~xor~val[p]}{deg[x]}$

转化为:

$f[x]*deg[x]=\sum f[y]~xor~val[p]$

由于本题有重边或者自环,具有后效性,因此不能直接求解。

每一位进行高斯消元:

$f[x]*deg[x]=\sum\limits_{val[p]=1}(1-f[y])+\sum\limits_{val[p]=0}f[y]$

变量放左边,常量放右边

$f[x]*deg[x]+\sum\limits_{val[p]=1}f[y]-\sum\limits_{val[p]=0}f[y]=\sum\limits_{val[p]=1}1$

高斯消元乱搞即可。

注意$f[n]=0$

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
#define eps 1e-6
using namespace std;
const int M=1e4+10,N=105;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,w,next;}a[M<<1];int len,last[N],deg[N];
inline void ins(int x,int y,int w){a[++len]=(edge){y,w,last[x]};last[x]=len;}
double d[N][N],ans;int n,m,mx;
inline void gauss()
{
    for(int i=1;i<n;i++)
    {
        int x=i;
        for(int j=i+1;j<n;j++)if(fabs(d[j][i])>fabs(d[x][i]))x=j;
        //if(fabs(d[x][i])<eps)continue;
        for(int j=1;j<=n+1;j++)swap(d[x][j],d[i][j]);
        for(int k=1;k<n;k++)
            if(k!=i)
            {
                double tmp=d[k][i]/d[i][i];
                for(int j=n+1;j>=i;j--)
                    d[k][j]-=tmp*d[i][j];
            }
    }
     
}
int main()
{
    qr(n),qr(m);ans=0;mx=0;
    for(int i=1,x,y,w;i<=m;i++){qr(x),qr(y),qr(w),ins(x,y,w),++deg[x],mx=max(mx,w);if(x^y)ins(y,x,w),++deg[y];}
    for(int p=1;p<=mx;p<<=1)
    {
        d[n][n]=1;//d[n][n+1]=0;
        for(int x=1;x<n;x++)
        {
            d[x][x]=deg[x];
            for(int k=last[x];k;k=a[k].next)
            {
                int y=a[k].y;
                if(a[k].w&p)++d[x][n+1],++d[x][y];
                else --d[x][y];
            }
        }
        gauss();
        ans+=d[1][n+1]/d[1][1]*p;
        memset(d,0,sizeof(d));
    }
    printf("%.3lf\n",ans);
    return 0;
}