【题意】给定n个点m条边的带边权无向连通图（有重边和自环），在每个点随机向周围走一步，求1到n的期望路径异或值。n<=100，wi<=10^9。

【算法】期望+高斯消元

【题解】首先异或不满足期望的线性，所以考虑拆位。

对于每一个二进制位，经过边权为0仍是x，经过边权为1变成1-x（转化成减法才满足期望的线性）。

设f[x]表示点x到n的路径xor期望，f[n]=0，根据全期望公式：

$$f[i]=\sum_{j}\frac{f[j]}{out[i]}\ \ , \ \ w(i,j)=0$$

$$f[i]=\sum_{j}\frac{1-f[j]}{out[i]}\ \ , \ \ w(i,j)=1$$

因为有循环所以用高斯消元求解，复杂度O(n^3*log wi)。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=110;struct edge{
    int v,w,from;}e[maxn*maxn*2];int n,m,first[maxn],tot,out[maxn];long double a[maxn][maxn],ans;void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;out[u]++;}void gauss(){    for(int i=1;i
          
           fabs(a[r][i]))r=j;        if(r!=i)for(int j=i;j<=n+1;j++)swap(a[i][j],a[r][j]);        for(int j=i+1;j<=n;j++)            for(int k=n+1;k>=i;k--)                a[j][k]-=a[j][i]/a[i][i]*a[i][k];    }    for(int i=n;i>=1;i--){        for(int j=i+1;j<=n;j++)a[i][n+1]-=a[i][j]*a[j][n+1];        a[i][n+1]/=a[i][i];    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        int u,v,w;        scanf("%d%d%d",&u,&v,&w);        insert(u,v,w);        if(u!=v)insert(v,u,w);//    }    for(int k=0;k<=30;k++){        memset(a,0,sizeof(a));//         for(int x=1;x
          
         
        
       
      

 

注意：

1.方程组右边是常数项。

2.自环不要重复加边。