BZOJ-3143: [Hnoi2013]游走

[文章目录]

Description

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

等价于求每条边的经过期望次数,从小到大排序标号,统计贡献即为答案。
等价于求每个点的期望经过次数,设为f[x],每个点的度数设为d[x]
那么可以得到一堆方程式:f[x]=f[to1]/d[to1]+f[to2]/d[to2]+...f[tom]/do[tom]
f[1]=1+...
f[n]=1
高斯消元即可。
对于double的高斯消元,由于有精度问题,每次要找当前位置最大的一个进行消元。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 510
int n,m,d[510],a[N*N],b[N*N];
double f[510][510],g[N*N];
int head[N],to[N*N],nxt[N*N],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",a+i,b+i);
        add(a[i],b[i]); add(b[i],a[i]);
        d[a[i]]++; d[b[i]]++;
    }
    for(i=1;i<=n;++i)
    {
        f[i][i]=1;
        for(j=head[i];j;j=nxt[j]) f[i][to[j]]=-1.0/d[to[j]];
    }
    for(i=1;i<=n;++i) f[i][n]=f[n][i]=0;
    f[1][n+1]=f[n][n+1]=f[n][n]=1;
    int k; double t;
    for(i=1;i<=n;++i)
    {
        t=fabs(f[i][i]); k=i;
        for(j=i+1;j<=n;++j) if(fabs(f[j][i])>t) t=f[j][i],k=j;
        for(j=i;j<=n+1;++j) swap(f[i][j],f[k][j]);
        for(k=n+1;k>=i;--k) f[i][k]/=f[i][i];
        for(j=1;j<=n;++j) if(j!=i)
        {
            t=f[j][i];
            for(k=i;k<=n+1;++k) f[j][k]-=t*f[i][k];
        }
    }
    for(i=1;i<=m;++i)
    {
        if(a[i]!=n) g[i]+=f[a[i]][n+1]/d[a[i]];
        if(b[i]!=n) g[i]+=f[b[i]][n+1]/d[b[i]];
    }
    sort(g+1,g+m+1);
    for(t=0,i=1;i<=m;++i) t+=g[i]*(m-i+1);
    printf("%.3lf",t);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注