题目链接 首先，我们想要求总的期望，那么我们发现如果我们能求出每条边的期望，之后对所有边的期望排序，贪心地给期望经过次数多的边赋小的编号，给期望经过次数少的边赋大的编号即可。 那么我们需要考虑如何求所有边的期望经过次数。 我们发现，每条边的期望次数是 dpxdegx+dpydegy d p x d e g x + d p y d e g y ，其中 x x 和yy是当前边的两个端点， dpi d p i 数组表示点 i i 的期望经过次数，degidegi表示在无向图中点 i i 的度数。 我们发现degdeg数组我们可以在读入这些边的时候顺便处理出来，那么我们只需要求出每个点期望经过的次数即可了。 那么我们考虑如何求每个点的期望经过次数。我们发现，每个点的期望经过次数是 dpv=∑v到u有边u dpudegu d p v = ∑ u v 到 u 有 边 d p u d e g u 。特别地，根据题意， n n 号点经过并且只经过一次，所以dpn=1dpn=1。另外， 1 1 号点为起点，一开始就会经过一次，所以11号点的期望步数是 dp1=∑1到u有边u dpudegu+1 d p 1 = ∑ u 1 到 u 有 边 d p u d e g u + 1 。 我们发现，我们可以对每个点列一个方程，这样可以高斯消元解出每一个点的期望经过次数。有了每个点的期望经过次数之后，我们可以通过之前的讲解求出每条边的期望步数并贪心地给边编号，最后统计答案。 思路就是这样子，实现的时候我觉得在高斯消元时要注意一下细节，特别是对于 n n 号点，它的dpdp值是 1 1 ，但是我们在实际操作时把第nn行只有 dpn d p n 的系数设为 1 1 ，其他的所有系数都设为00，包括增广的那一列也是0。但是这样我们会发现最后一个式子成了 dpn=0 d p n = 0 。这样做是因为我们在考虑每个点给每条边的影响时， n n 号点是不会对与它相连的边产生贡献的，因为到了nn号点就不能再返回了，所以为了正确地统计边的期望经过次数，强制将点 n n 的期望经过次数设为了00，实际上应该是 1 1 的。而把dpndpn的系数设为 1 1 的原因是为了避免在做nn个元的高斯消元时 dp(n+1)/dpn d p ( n + 1 ) / d p n 时因为除以 0 0 <script id="MathJax-Element-32" type="math/tex">0</script>而RE。主要还是我高斯消元写得有点少。 最后是代码：
#include <bits/stdc++.h> using namespace std; int n,m,hed[1000],cnt; struct node { int from,to,next; }a[5000010]; double dp[1001],b[502][502],ans,e[5000100],deg[510]; void add(int from,int to) { a[++cnt].to=to; a[cnt].from=from; a[cnt].next=hed[from]; hed[from]=cnt; } void gauss() { for(int i=1;i<=n;++i) { int r=i; for(int j=i+1;j<=n;++j) { if(abs(b[j][i])>abs(b[r][i])) r=j; } if(r!=i) swap(b[r],b[i]); for(int j=i+1;j<=n;++j) { double t=b[j][i]/b[i][i]; for(int k=i;k<=n+1;++k) b[j][k]-=t*b[i][k]; } } for(int i=n;i>=1;--i) { for(int j=n;j>i;--j) b[i][n+1]-=b[i][j]*b[j][n+1]; b[i][n+1]/=b[i][i]; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int x,y; scanf("%d%d",&x,&y); add(x,y);//正向边和反向边只算一条 ++deg[x]; ++deg[y]; } for(int i=1;i<=n-1;++i) b[i][i]=-1; for(int i=1;i<=m;++i) { b[a[i].from][a[i].to]+=(double)1.0/deg[a[i].to]; b[a[i].to][a[i].from]+=(double)1.0/deg[a[i].from]; } for(int i=1;i<=n-1;++i) b[n][i]=0; b[n][n]=1; b[1][n+1]=-1; gauss(); for(int i=1;i<=m;++i) e[i]=b[a[i].from][n+1]/deg[a[i].from]+b[a[i].to][n+1]/deg[a[i].to]; sort(e+1,e+m+1); for(int i=1;i<=m;++i) ans+=e[i]*(m-i+1); printf("%.3lf\n",ans); return 0; }