BZOJ3143/HNOI2013/游走

Posted on By 二价氢

定义:\(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;
}