60355

【HNOI2013】游走

题面

https://www.luogu.org/problem/P3232

题解

一道令我印象深刻的广为人知的图上随机游走模型,当时写的时候没有明白为什么,现在重新补一下。

首先,一眼贪心。找出每条边期望经过的次数,然后排个序,编号倒着给,这样就达到了“总分的期望值最小”。

求每条边$(u,v)$期望经过的次数,分为$u \to v$和$v \to u$,设$p_u$为$u$期望经过的次数,$p(u,v)=\frac{p_u}{d_u}+\frac{p_v}{d_v}$。

求每个点期望经过的次数,还是一个邻接矩阵$M$(和别的题一样的建法)。列向量$P$乘上这个矩阵。

设$sum=\sum_{i=0}^{INF}{PM^i}$

列向量$sum$的最后一个$n$是没有意义的,但是$[1..n-1]$都是有意义的,就是代表这个点期望经过的次数。

因为$P[1..n]$前$n-1$位最后会趋向于$0$,所以$sum$前$n-1$位最后会趋向于一个定值,我们要利用高斯消元在$O(n^3)$求出它。

因为$sum$是一个等比数列和的形式,所以我们可以用大神教我们的等比数列求和公式求得$sum$(需要用矩阵求逆),这样复杂度就对了。

等等,让我看一下,代码没有用矩阵求逆啊。为什么就搞出来了呢?

不要想着把$(M-I)$除过去,想着把$(M-I)$看成一个多元一次方程的系数,把$PM^{INF}-P$看成这个方程组的右侧的值,然后高斯消元,求得就是$sum$的值了。

想出来这个超级激动啊,嘤嘤嘤。

#include<cstdio> #include<iostream> #include<vector> #include<cmath> #include<cstring> #include<algorithm> #define ri register int #define N 505 #define double long double #define M 130000 #define INF 1000000007 using namespace std; int n,m; vector<int> to[N]; double d[N]; double mat[N][N],p[N],ans=0; int a[M],b[M],id[M]; bool cmp(int x,int y) { return p[a[x]]/d[a[x]]+p[b[x]]/d[b[x]]<p[a[y]]/d[a[y]]+p[b[y]]/d[b[y]]; } void guess() { for (ri i=1;i<=n;i++) { int p=-1; double maxa=0; for (ri j=i;j<=n;j++) if (fabs(mat[j][i])>maxa) maxa=fabs(mat[j][i]),p=j; for (ri j=1;j<=n+1;j++) swap(mat[i][j],mat[p][j]); for (ri j=i+1;j<=n;j++) { double dv=mat[j][i]/mat[i][i]; for (ri k=1;k<=n+1;k++) mat[j][k]-=mat[i][k]*dv; } } p[n]=mat[n][n+1]/mat[n][n]; for (ri i=n-1;i>=1;i--) { for (ri j=i+1;j<=n;j++) mat[i][n+1]-=p[j]*mat[i][j]; p[i]=mat[i][n+1]/mat[i][i]; } } int main(){ scanf("%d %d",&n,&m); for (ri i=1;i<=m;i++) { scanf("%d %d",&a[i],&b[i]); to[a[i]].push_back(b[i]); to[b[i]].push_back(a[i]); } for (ri i=1;i<=n;i++) d[i]=to[i].size(); d[n]=INF; for (ri i=1;i<=n-1;i++) { for (ri j=0;j<to[i].size();j++) { int x=to[i][j]; if (x!=n) mat[i][x]=1.0/d[x]; } mat[i][i]=-1.0; } mat[1][n]=-1.0; p[n]=0; n--; guess(); for (ri i=1;i<=m;i++) id[i]=i; sort(id+1,id+m+1,cmp); ans=0; for (ri i=1;i<=m;i++) ans+=(p[a[id[i]]]/d[a[id[i]]]+p[b[id[i]]]/d[b[id[i]]])*(double)(m-i+1); printf("%.3Lf",ans); }

来源:博客园

作者:HellPix

链接:https://www.cnblogs.com/shxnb666/p/11426032.html

Recommend