按位考虑一下，然后相当于考虑最终为1的概率
如果这条边这位是1，那么f[x]+=(1-f[y])/degree[x]，否则f[x]+=f[y]/degree[x]
高斯消元一下即可
复杂度n^3 log n
不知道为什么开始脑抽以为复杂度是n^4的……
#include<iostream> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<cstdlib> #include<cstdio> #include<map> #include<bitset> #include<set> #include<stack> #include<vector> #include<queue> using namespace std; #define MAXN 110 #define MAXM 20010 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 struct vec{ int to; int fro; int v; }; int n,m; vec mp[MAXM]; int tai[MAXN],cnt; double a[MAXN][MAXN]; int d[MAXN]; double ans; inline void be(int x,int y,int z){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; mp[cnt].v=z; } void gs(){ int i,j,k; for(i=1;i<=n;i++){ if(fabs(a[i][i])<eps){ for(j=i+1;j<=n;j++){ if(fabs(a[j][i])>eps){ for(k=1;k<=n+1;k++){ swap(a[i][k],a[j][k]); } break; } } } if(fabs(a[i][i])>eps){ for(j=1;j<=n;j++){ if(i!=j){ double t=-a[j][i]/a[i][i]; for(k=1;k<=n+1;k++){ a[j][k]+=a[i][k]*t; } } } } } } int main(){ int i,x,y,z; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); be(x,y,z); d[x]++; if(x!=y){ d[y]++; be(y,x,z); } } for(z=0;z<31;z++){ memset(a,0,sizeof(a)); for(x=1;x<n;x++){ a[x][x]-=1.; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(mp[i].v&(1<<z)){ a[x][y]+=-1./d[x]; a[x][n+1]+=-1./d[x]; }else{ a[x][y]+=1./d[x]; } } } a[n][n]=1.; gs(); ans+=(1<<z)*(a[1][n+1]/a[1][1]); } printf("%.3lf\n",ans); return 0; } /* */
