[BZOJ3143][Hnoi2013]游走（概率期望+高斯消元）

2019-11-11 06:20:12

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

感觉这种互相之间都有关系的题目就是列一坨式子然后用高斯消元搞一下… 设点i的期望到达次数为f(i)，点i的度为d(i)，那么f(i)=∑(i,j)∈Ef(j)d(j) $f(i)=/sum/limits_{(i,j)/in E}{f(j)/over d(j)}$ 就是相当于其它的点走到这个点注意这里点n是不能计算的，因为n不会再往其它的点走这样的话得出了n-1个方程，高斯消元求出f(i)的值然后计算每一条边的期望经过次数，(u,v)=f(u)d(u)+f(v)d(v) $(u,v)={f(u)/over d(u)}+{f(v)/over d(v)}$ 这里点n同样不能统计将边的期望排序然后从大到小分配编号就行了

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 505const double eps=1e-12;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}int n,m,x,y;struct data{int x,y;}e[N*N];int tot,point[N],nxt[N*N*2],v[N*N*2];double ans;double d[N],f[N],a[N][N],b[N],ex[N*N*2];void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void guass(){ for (int i=1;i<n;++i) { int num=i; for (int j=i+1;j<n;++j) if (dcmp(a[num][i]-a[j][i])<0) num=j; for (int j=1;j<n;++j) swap(a[i][j],a[num][j]); swap(b[i],b[num]); for (int j=i+1;j<n;++j) if (dcmp(a[j][i])) { double t=a[j][i]/a[i][i]; for (int k=1;k<n;++k) a[j][k]-=a[i][k]*t; b[j]-=b[i]*t; } } for (int i=n-1;i>=1;--i) { for (int j=i+1;j<=n;++j) b[i]-=a[i][j]*f[j]; f[i]=b[i]/a[i][i]; }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;++i) { scanf("%d%d",&x,&y); d[x]+=1.0;d[y]+=1.0; add(x,y);add(y,x); e[i].x=x,e[i].y=y; } for (int i=1;i<n;++i) { a[i][i]=1.0; for (int j=point[i];j;j=nxt[j]) if (v[j]!=n) a[i][v[j]]=-1/d[v[j]]; } b[1]=1.0; guass(); for (int i=1;i<=m;++i) ex[i]=f[e[i].x]/d[e[i].x]+f[e[i].y]/d[e[i].y]; sort(ex+1,ex+m+1); for (int i=1;i<=m;++i) ans+=ex[i]*(m-i+1.0); PRintf("%.3lf/n",ans);}

上一篇：解决:The project cannot be built until build path

下一篇：谈谈调试（Debug）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注