[bzoj3143] [洛谷P3232] [HNOI2013] 游走

Description###

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

Input###

第一行是正整数N和M，分别表示该图的顶点数和边数，接下来M行每行是整数u，v(1<=u,v<=N)，表示顶点u与顶点v之间存在一条边。输入保证30%的数据满足N<=10，100%的数据满足2<=N<=500且是一个无向简单连通图。

Output###

仅包含一个实数，表示最小的期望值，保留3位小数。

Sample Input###

3 3

2 3

1 2

1 3

Sample Output###

3.333

HINT###

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

想法##

果断高斯消元解期望方程啊。

如果我们知道了每条边期望被经过的次数，那么贪心按期望值从小到大、编号从大到小编就好了

但是每条边期望被经过的次数并不好搞，每个点的期望经过次数是可以搞出来的

列方程组的时候注意，1号点最初的期望值就有1，n号点只能进不能出

假设某条边两端的点为u,v，每个点期望被经过次数为e[i]，每个点的度数为d[i]

则这条边期望被经过的次数为 \(e[u]/d[u] + e[v]/d[v]\)

注意要特判一下，如果u、v中某一个为n的话，这条边只能从那个不是n的点过来，所以被经过的期望为\(e[u]/d[u]\)或\(e[v]/d[v]\)

然后排个序贪心就行啦

代码##

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#define eps 0.001

using namespace std;

const int N = 505;

typedef double db[N][N];

int n,m;

void gauss(db A){

    for(int i=1;i<=n;i++){

        int r=i;

        for(int j=i+1;j<=n;j++)

            if(fabs(A[j][i])-fabs(A[r][i])>eps) r=j;

        for(int j=i;j<=n;j++) swap(A[i][j],A[r][j]);

        for(int j=i+1;j<=n;j++){

            double f=A[j][i]/A[i][i];

            for(int k=i;k<=n+1;k++) A[j][k]-=f*A[i][k];

        }

    }

    for(int i=n;i>0;i--){

        for(int j=i+1;j<=n;j++)

            A[i][n+1]-=A[i][j]*A[j][n+1];

        A[i][n+1]/=A[i][i];

    }

}

db a;

struct edge{

    int u,v;

    double f;

    edge(int u=0,int v=0,double f=0.0):u(u),v(v),f(f) {}

    bool operator < (const edge &b) const { return f>b.f; }

}d[N*N/2];

int s[N];

int main()

{

    int x,y;

    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++){

        scanf("%d%d",&x,&y);

        if(x>y) swap(x,y);

        d[i]=edge(x,y);

        if(y==n) a[y][x]=1.0;

        else a[x][y]=a[y][x]=1.0;

        s[x]++; s[y]++;

    }

    for(int i=1;i<=n;i++) {

        a[i][i]=1.0;

        if(i==1) a[i][n+1]=1.0;

        for(int j=1;j<=n;j++){

            if(j==i) continue;

            if(a[i][j]) a[i][j]*=-1.0/s[j];

        }

    }

    gauss(a);

    for(int i=0;i<m;i++){

        if(d[i].v==n) d[i].f=a[d[i].u][n+1]*1.0/s[d[i].u];

        else d[i].f=a[d[i].u][n+1]*1.0/s[d[i].u]+a[d[i].v][n+1]*1.0/s[d[i].v];

    }

    sort(d,d+m);

    double ans=0.0;

    for(int i=0;i<m;i++) ans+=d[i].f*(i+1);

    printf("%.3lf\n",ans); 

    return 0;

}

巴特西