BZOJ2337: [HNOI2011]XOR和路径 期望概率dp 高斯

这个题让我认识到我以往对于图上期望概率的认识是不完整的，我之前只知道正着退还硬生生的AC做过的所有图，那么现在让我来说一下逆退，一般来说对于概率性的东西都只是正推，因为有了他爸爸才有了他，而对于期望性的东西可以说是从终点开始每个点都是以这个点为起点到终点的期望，那么就可以是有本节点开花遗传和继承。

本题中说求异或，那么根据异或的一般思路，一位一位的搞，每一位不是一就是二我么可以求从这个点到终点这一位是1的期望也就是概率了

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 105
#define M 10005
using namespace std;
typedef double D;
D a[N][N],b[N],ans;
int head[N],t,bang[N],n,m;
struct T
{
   int to,next,w;
}c[M<<1];
inline void add(int x,int y,int z)
{
   c[++t].to=y;
   c[t].next=head[x];
   head[x]=t;
   bang[x]++;
   c[t].w=z;
}
inline void Init()
{
   scanf("%d%d",&n,&m);
   for(int i=1;i<=m;i++)
   {
     int x,y,z;
     scanf("%d%d%d",&x,&y,&z);
     add(x,y,z);
     if(x!=y)
      add(y,x,z);
   }
}
inline D abs(D x)
{
   return x<0.0?0.0-x:x;
}
inline void swap(D &x,D &y)
{
   D temp=x;
   x=y;
   y=temp;
}
void gauss()
{
   for(int i=1,k=1;i<=n;i++,k++)
   {
     int temp=i;
     D need=abs(a[i][k]);
     for(int j=i+1;j<=n;j++)
      if(abs(a[j][k])>need)
       need=abs(a[j][k]),temp=j;
     if(temp!=i)
       for(int j=k;j<=n+1;j++)
        swap(a[temp][j],a[i][j]);
     for(int j=i+1;j<=n;j++)
     {
      need=a[j][k]/a[i][k];
      for(int l=k;l<=n+1;l++)
       a[j][l]-=a[i][l]*need;
     }
   }
   for(int i=n;i>0;i--)
   {
     for(int j=i+1;j<=n;j++)
      a[i][n+1]-=b[j]*a[i][j];
     b[i]=a[i][n+1]/a[i][i];
   }
}
void job(int now)
{
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n+1;j++)
     a[i][j]=0.0;
   for(int x=1;x<n;x++)
   {
     for(int i=head[x];i;i=c[i].next)
      if(c[i].w&now)
       a[x][c[i].to]-=1.0/bang[x],a[x][n+1]-=1.0/bang[x];
      else
       a[x][c[i].to]+=1.0/bang[x];
     a[x][x]-=1.0;
   }
   a[n][n]=1.0;
   a[n][n+1]=0.0;
   gauss();
   ans+=b[1]*now;
}
inline void work()
{
   for(int i=0;i<30;i++)
    job(1<<i);
   printf("%.3lf",ans);
}
int main()
{
   Init();
   work();
   return 0;
}