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

2019-11-11 04:49:53

字體：大中小

供稿：網(wǎng)友

題目描述

傳送門(mén)

題解

感覺(jué)這種互相之間都有關(guān)系的題目就是列一坨式子然后用高斯消元搞一下… 設(shè)點(diǎn)i的期望到達(dá)次數(shù)為f(i)，點(diǎn)i的度為d(i)，那么f(i)=∑(i,j)∈Ef(j)d(j) $f(i)=/sum/limits_{(i,j)/in E}{f(j)/over d(j)}$ 就是相當(dāng)于其它的點(diǎn)走到這個(gè)點(diǎn) 注意這里點(diǎn)n是不能計(jì)算的，因?yàn)閚不會(huì)再往其它的點(diǎn)走這樣的話得出了n-1個(gè)方程，高斯消元求出f(i)的值然后計(jì)算每一條邊的期望經(jīng)過(guò)次數(shù)，(u,v)=f(u)d(u)+f(v)d(v) $(u,v)={f(u)/over d(u)}+{f(v)/over d(v)}$ 這里點(diǎn)n同樣不能統(tǒng)計(jì) 將邊的期望排序然后從大到小分配編號(hào)就行了

代碼

#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);