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

2019-11-11 06:20:12

字體：大中小

來源：轉載

供稿：網(wǎng)友

題目描述

傳送門

題解

感覺這種互相之間都有關系的題目就是列一坨式子然后用高斯消元搞一下… 設點i的期望到達次數(shù)為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)的值然后計算每一條邊的期望經(jīng)過次數(shù)，(u,v)=f(u)d(u)+f(v)d(v) $(u,v)={f(u)/over d(u)}+{f(v)/over d(v)}$ 這里點n同樣不能統(tǒng)計將邊的期望排序然后從大到小分配編號就行了

代碼

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