首页 > 代码库 > 【BZOJ2337】[HNOI2011]XOR和路径 期望DP+高斯消元
【BZOJ2337】[HNOI2011]XOR和路径 期望DP+高斯消元
【BZOJ2337】[HNOI2011]XOR和路径
Description
题解：异或的期望不好搞？我们考虑按位拆分一下。
我们设f[i]表示到达i后，还要走过的路径在当前位上的异或值得期望是多少（妈呀好啰嗦），设d[i]表示i的度数。然后对于某条边(a,b)，如果它的权值是1，那么f[b]+=(1-f[a])/d[a]；如果它的权值是0，那么f[b]+=f[a]/d[a]，然后我们移个项，就变成了一堆方程组求解，直接高斯消元。
别忘了f[n]=0！
#include <cstdio>#include <cstring>#include <iostream>#include <cmath>using namespace std;typedef long double ld;int d[110];ld v[110][110],ans;int n,m;int pa[10010],pb[10010],pc[10010];ld calc(int x){ int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n+1;j++) v[i][j]=0; for(i=1;i<=m;i++) { if(pc[i]&x) { v[pa[i]][pb[i]]+=1,v[pa[i]][n+1]+=1; if(pa[i]!=pb[i]) v[pb[i]][n+1]+=1,v[pb[i]][pa[i]]+=1; } else { v[pa[i]][pb[i]]-=1; if(pa[i]!=pb[i]) v[pb[i]][pa[i]]-=1; } } for(i=1;i<=n;i++) v[i][i]+=d[i]; for(i=1;i<=n+1;i++) v[n][i]=0; v[n][n]=1; for(i=1;i<=n;i++) { for(j=i;j<=n;j++) if(fabs(v[i][i])<fabs(v[j][i])) for(k=i;k<=n+1;k++) swap(v[i][k],v[j][k]); if(fabs(v[i][i])<1e-7) continue; for(j=n+1;j>=i;j--) v[i][j]/=v[i][i]; for(j=1;j<=n;j++) if(i!=j) { for(k=1;k<=n+1;k++) if(k!=i) v[j][k]-=v[j][i]*v[i][k]; v[j][i]=0; } } return v[1][n+1];}int main(){ int i,a,b,c; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&pa[i],&pb[i],&pc[i]); d[pa[i]]++; if(pa[i]!=pb[i]) d[pb[i]]++; } for(i=1;i<1<<30;i<<=1) ans+=i*calc(i); printf("%.3lf",(double)ans); return 0;}【BZOJ2337】[HNOI2011]XOR和路径 期望DP+高斯消元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。