来自 技术 2019-03-16 的文章

[HNOI2011]XOR和路径 - cloud_9

Description:

Hint:

100%的数据满足2≤N≤100,M≤10000

Solution:

显然是高斯消元解方程组

怎么列? 考虑按位计算,现在处理到第t位

设\(f[i]\)为走到i点这一位为1的期望

则有\(f[i]=\frac{\sum_{w(i,j)\&t==0}\ \ \ \ \ f[j]+\sum_{w(i,j)\&t==1}\ \ \ (\ \ \ 1-f[j])} {deg[i]}\)

\(deg[i]*f[i]-\sum_{w(i,j)\&t==0}\ \ \ f[j] +\sum_{w(i,j)\&t==1}\ \ \ f[j] =\sum_{w(i,j)\&t==1} 1\)

注意第n行只有n系数为1,等式右边为0

每一位算一次再把a[1]加起来就是答案

高斯消元老是写错...

#include <map>#include <set>#include <stack>#include <cmath>#include <queue>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define ls p<<1 #define rs p<<1|1using namespace std;typedef long long ll;const int mxn=5005;const double eps=1e-2;int n,m,cnt,d[mxn*1000],p[mxn*1000],q[mxn*1000],hd[mxn*1000];double ans,res[mxn*1000],a[mxn][mxn];inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f;}inline int chkmax(int &x,int y) {if(x<y) x=y;}inline int chkmin(int &x,int y) {if(x>y) x=y;}struct ed { int to,nxt,w;}tt[mxn<<7];inline void add(int u,int v,int w) { tt[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;}int main(){ n=read(); m=read(); int u,v,w,mx=0; for(int i=1;i<=m;++i) { u=read(); v=read(); w=read(); add(u,v,w); ++d[v]; if(u!=v) add(v,u,w),++d[u]; chkmax(mx,w); p[i]=u; q[i]=v; } for(int t=1;t<=mx;t<<=1) { for(int i=1;i<=n;++i) for(int j=1;j<=n+1;++j) a[i][j]=0.0; a[n][n]=1.0; for(int i=1;i<n;++i) { a[i][i]=d[i]; for(int j=hd[i];j;j=tt[j].nxt) { int v=tt[j].to; if(!(tt[j].w&t)) a[i][v]--; else a[i][v]++,a[i][n+1]++; } } for(int i=1;i<=n;++i) { int now=i; double tp=a[i][i]; for(int j=i+1;j<=n;++j) if(fabs(a[j][i])-fabs(tp)>eps) now=j,tp=a[j][i]; if(now!=i) for(int j=1;j<=n+1;++j) swap(a[i][j],a[now][j]); for(int j=n+1;j>=i;--j) a[i][j]/=a[i][i]; for(int j=1;j<=n;++j) if(i!=j&&a[j][i]) for(int k=n+1;k>=i;--k) a[j][k]-=a[j][i]*a[i][k]; } ans+=1.0*a[1][n+1]*(double) t; } printf("%.3lf\n",ans); return 0;}

标签:   电子邮件手机客户端      网站登录失败   
上一篇:一篇入门 — Gatling 性能测试手册 - 旻天clock
下一篇:没有了