题目传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=3143
我们令 $P_i$ 表示从第 i 号点出发的期望次数则 $P_n$ 显然为 $0$
对于 $P_2~P_{n-1}$, 则有 $P_i= \sum \frac{P_j} {d_j}$, 其中节点 j 与节点 i 有边相连,$d_j$ 表示节点 j 的度数
对于 $P_1$, 则有 $P_i=1+ \sum \frac{P_j} {d_j}$
不难发现其实就是一个 $n$ 元一次方程组, 我们可以通过高斯消元求出每一个 $P_i$
对于一条边 $(x,y)$, 经过这条边的期望次数为 $ \frac {P_x} {d_x} + \frac {P_y} {d_y}$, 我们设此值为 $p_i$
我们把期望经过次数从大到小排序, 则答案为 $\sum_{i=1}^{n} p_i \times i$
然后就做完了
AC 代码如下:
- #include<bits/stdc++.h>
- #define M 505
- using namespace std;
- int a[M][M]={0},n,m;
- double f[M][M]={0},p[M]={0},du[M]={0};
- void solve(){
- for(int i=1;i<=n;i++){
- for(int j=i+1;j<=n;j++){
- double x=f[j][i]/f[i][i];
- for(int k=i;k<=n+1;k++)
- f[j][k]-=x*f[i][k];
- }
- }
- for(int i=n;i;i--){
- for(int j=i+1;j<=n;j++)
- f[i][n+1]-=f[i][j]*p[j];
- p[i]=f[i][n+1]/f[i][i];
- }
- }
- int X[M*M]={0},Y[M*M]={0}; double hh[M*M]={0};
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- int x,y; scanf("%d%d",&x,&y);
- a[x][y]=a[y][x]=1;
- du[x]++; du[y]++;
- X[i]=x; Y[i]=y;
- }
- f[1][n+1]=-1; f[n][n]=1;
- for(int i=1;i<n;i++){
- f[i][i]=-1;
- for(int j=1;j<=n;j++) if(a[i][j])
- f[i][j]=1/du[j];
- }
- solve();
- for(int i=1;i<=m;i++)
- hh[i]=p[X[i]]/du[X[i]]+p[Y[i]]/du[Y[i]];
- sort(hh+1,hh+m+1);
- double ans=0;
- for(int i=1;i<=m;i++)
- ans+=hh[i]*(m-i+1);
- printf("%.3lf\n",ans);
- }
来源: http://www.bubuko.com/infodetail-2514806.html