定义:\(D_i\)表示点\(i\)的度,\(x_i\)表示点\(i\)的期望到达次数
我们知道,由于从点$i$出发到与之相连的每条边的概率为\(\frac{1}{D_i}\)
所以,\(x_j=\sum_{i\textrm{与}j\textrm{直接连通}}\frac{1}{D_i}\)
同时,因为1号点为起点,所以其要加上1的期望经过次数
因此,我们可列方程组如下:
\[\left\{\begin{array}{lll} x_1&=&1+\sum_{i\textrm{与}1\textrm{直接连通}}\frac{1}{D_i}\\ x_2&=&\sum_{i\textrm{与}2\textrm{直接连通}}\frac{1}{D_i}\\ &\vdots&\\ x_{n-1}&=&\sum_{i\textrm{与}n-1\textrm{直接连通}}\frac{1}{D_i}\\ \end{array}\right.\]注意,因为到了点\(n\)之后就结束了,所以点\(n\)对其余的点没有贡献
通过每个点期望经过次数,我们可以求出每条边期望经过次数,用贪心排序后相加即得结果
像这样的利用方程求期望的方法,在NOIp2013的初赛题中也有出现
额外要注意的是eps
的取值,太大太小都会导致Wrong Answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <utility>
using namespace std;
//-- 浮点数比较模板
const double eps=1e-10;
bool _l (double a,double b){return a < b-eps ;}
bool _g (double a,double b){return a > b+eps ;}
bool _le (double a,double b){return a < b+eps ;}
bool _ge (double a,double b){return a > b-eps ;}
bool _eq (double a,double b){return fabs(a-b)< eps ;}
//-- END
const int maxn=505;
double eq[maxn][maxn],sol[maxn];
int d[maxn];
double edg[maxn*maxn];
vector <pair<int,int> > E[maxn];
typedef vector <pair<int,int> >::iterator ii;
int n,e;
int main()
{
int u,v;
scanf("%d%d",&n,&e);
for (int i=1;i<=e;i++)
{
scanf("%d%d",&u,&v);
d[u]++;d[v]++;
E[u].push_back(make_pair(v,i));
E[v].push_back(make_pair(u,i));
}
for (int i=1;i<n;i++)
{
eq[i][i]=1;
for (ii k=E[i].begin();k!=E[i].end();k++)
{
if (k->first==n)
continue;
eq[i][k->first]-=1.0/d[k->first];
}
}
n--;
eq[1][n+1]=1;
int k=1;
double ratio;
for (int i=1;i<=n;i++)
{
int p=0;
for (int j=k;j<=n;j++)
if (!_eq(eq[i][k],0))
{
p=j;
break;
}
if (!p)
continue;
for (int j=1;j<=n+1;j++)
swap(eq[p][j],eq[k][j]);
for (int j=k+1;j<=n;j++)
{
ratio=eq[j][i]/eq[k][i];
for (int l=1;l<=n+1;l++)
eq[j][l]-=eq[k][l]*ratio;
}
k++;
}
for (int i=n;i;i--)
{
sol[i]=eq[i][n+1];
for (int j=i+1;j<=n;j++)
sol[i]-=sol[j]*eq[i][j];
sol[i]/=eq[i][i];
}
for (int i=1;i<=n;i++)
for (ii k=E[i].begin();k!=E[i].end();k++)
edg[k->second]+=sol[i]/d[i];
sort(&edg[1],&edg[e+1],_g);
double ans=0;
for (int i=1;i<=e;i++)
ans+=edg[i]*i;
printf("%.3lf\n",ans);
return 0;
}