Description:

一个无向连通图,顶点从 编号到 ,边从 编号到 。 小 在该图上进行随机游走,初始时小 号顶点,每一步小 以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 到达 号顶点时游走结束,总分为所有获得的分数之和。现在,请你对这 条边进行编号,使得小 获得的总分的期望值最小。



Solution:

如果我们求出了每条边经过次数的期望值,然后我们就可以按期望值贪心了。所以重点在于求期望值。
对于每条边我们可以拆成两条有向边,那么有:我们可以高斯消元,但是时间复杂度是 的。但是显然会

我们考虑到达每个点的次数的数学期望值,则有:

所以每条边的数学期望值:时间复杂度


Code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int N,M;

struct bian_
{
    int st;
    int to;
    double val;
}bian[250010]={{0,0,0}};

int du[510]={0};
double A[510]={0};

double fc[510][510]={{0}};

bool dcmp(double x)
{return fabs(x)<1e-10;}

void Gauss()
{
    for(int i=1;i<=N-1;i++)
    {
        int g=0;
        for(int j=i;j<=N-1;j++)
        {
            if(dcmp(fc[j][i])==false)
            {
                g=j;
                break;
            }
        }
        if(g==0) continue;
        swap(fc[g],fc[i]);
        for(int j=1;j<=N-1;j++)
            if(j!=i && dcmp(fc[j][i])==false)
            {
                double o=fc[j][i]/fc[i][i];
                for(int p=0;p<=N-1;p++)
                    fc[j][p]-=fc[i][p]*o;
            }
    }
    for(int i=1;i<N;i++)
        A[i]=fc[i][0]/fc[i][i];
    return;
}

bool cmp(struct bian_ a1,struct bian_ a2)
{return a1.val>a2.val;}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d",&bian[i].st,&bian[i].to);
        du[bian[i].st]++,du[bian[i].to]++;
    }
    for(int i=1;i<=M;i++)
    {
        if(bian[i].to==N || bian[i].st==N) continue;
        fc[bian[i].st][bian[i].to]=-(double)1/du[bian[i].to];
        fc[bian[i].to][bian[i].st]=-(double)1/du[bian[i].st];
    }
    for(int i=1;i<N;i++)
        fc[i][i]=1,fc[i][0]=(i==1);
    Gauss();
    for(int i=1;i<=M;i++)
        bian[i].val=A[bian[i].st]/du[bian[i].st]+A[bian[i].to]/du[bian[i].to];
    sort(bian+1,bian+M+1,cmp);
    double ans=0;
    for(int i=1;i<=M;i++)
        ans+=bian[i].val*i;
    printf("%.3lf",ans);
    return 0;
}