会了高斯消元这就是个水题
首先既然是XOR，那么肯定要把边权拆成二进制然后算
那么计算点1每一位到点n的期望大小
因为每一条边都是0或者1，那么规定f[i]为当前位i点到n点的XOR和期望大小（也可理解为到n点XOR和为1的概率），d[i]为i点的度数
显而易见，对于i的每一个邻点j，若边(i,j)为0，则f[i]+f[j]/d[i]，否则f[i]+(1-f[j])/d[i]。
则可以建立n元一次方程，每次解出f[1]即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
// <xor.cpp> - 03/20/16 07:50:43 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=102; int n; double a[MAXN][MAXN]; vector <pair<int,int> >b[MAXN]; void gauss(){ for(int i=1;i<=n;i++){ for(int k=i+1;k<=n;k++)if(abs(a[k][i])>abs(a[i][i]))swap(a[k],a[i]); for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i]; for(int k=i+1;k<=n;k++) for(int j=n+1;j>=i;j--)a[k][j]-=a[k][i]*a[i][j]; } for(int i=n;i;i--) for(int k=i-1;k;k--)a[k][n+1]-=a[k][i]*a[i][n+1]; } int main(){ freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); n=getint(); int m=getint(); for(int i=0;i<m;i++){ int u=getint(),v=getint(),w=getint(); b[u].push_back(make_pair(v,w)); if(u!=v)b[v].push_back(make_pair(u,w)); } double ANS=0.0; for(int k=0;k<31;k++){ for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++)a[i][j]=0.0; for(int i=1;i<n;i++){ a[i][i]=1; for(int j=0;j<b[i].size();j++){ if(b[i][j].second&1){ a[i][b[i][j].first]+=1.0/b[i].size(); a[i][n+1]+=1.0/b[i].size(); }else a[i][b[i][j].first]+=-1.0/b[i].size(); b[i][j].second>>=1; } } a[n][n]=1; gauss(); ANS+=a[1][n+1]*(1<<k); } printf("%.3lf",ANS); return 0; } |
说点什么