首页 > 代码库 > 【BZOJ】2337: [HNOI2011]XOR和路径
【BZOJ】2337: [HNOI2011]XOR和路径
【算法】期望+高斯消元
【题解】因为异或不能和期望同时运算,所以必须转为加乘
考虑拆位,那么对于边权为1取反,边权为0不变。
E(x)表示从x出发到n的路径xor期望。
对于点x,有E(x)=Σ(1-E(y))(边权1)||E(y)(边权0)/t[x] t[x]为x的度。
那么有n个方程,整体乘上t[x]确保精度,右项E(x)移到左边——方程可以各种变形。
每次计算完后*(1<<k)就是贡献。
逆推的原因在于n不能重复经过,而1能重复经过,所以如果计算“来源”不能计算n,而计算1也有困难。
所以逆推计算“去向”是最方便的。
那么定义E(n)=0。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int maxn=110; struct edge{int v,w,from;}e[maxn*maxn*2]; int first[maxn],n,m,tot,t[maxn]; long double a[maxn][maxn]; 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;t[u]++;} void gauss() { for(int i=1;i<=n;i++) { int r=i; for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[r][i]))r=j; if(r!=i)for(int j=i;j<=n+1;j++)swap(a[r][j],a[i][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-1;i>=1;i--) { for(int j=i+1;j<=n;j++) a[i][n+1]-=a[j][n+1]*a[i][j]; 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); } long double ans=0; for(int k=0;k<30;k++) { memset(a,0,sizeof(a)); for(int x=1;x<n;x++) { for(int i=first[x];i;i=e[i].from) { if(e[i].w&(1<<k)){a[x][e[i].v]-=1.0;a[x][n+1]-=1.0;} else a[x][e[i].v]+=1.0; } a[x][x]-=t[x]; } a[n][n+1]=0.0; gauss(); ans=(ans+a[1][n+1]*(1<<k)); } printf("%.3Lf",ans); return 0; }
【BZOJ】2337: [HNOI2011]XOR和路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。