BZOJ3141 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。

我们先把概率的DP转移方程列出来

发现因为是无向图，所以一定有方程转移是纠缠在一起的

然后我们就用高斯消元的方式解开方程组就可以得到答案了

#include<bits/stdc++.h>

using namespace std;

#define N 510

int n,m,out[N];

double p[N][N];

bool mp[N][N];

const double eps=1e-9;

struct Q{

    int x,y;

    double w;

}e[N*N];

bool cmp(const Q& a,const Q& b){

    return a.w>b.w;

}

void gauss(int n,double a[N][N]){

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

        int r=i;

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

            if(fabs(a[j][i])>fabs(a[r][i]))r=j;

        if(r!=i)for(int j=0;j<=n;j++)swap(a[r][j],a[i][j]);

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

            double f=a[k][i]/a[i][i];

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

        }

    }

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

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

            a[i][n]-=a[j][n]*a[i][j];

        a[i][n]/=a[i][i];

    }

}

int main(){

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

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

        scanf("%d%d",&e[i].x,&e[i].y);

        e[i].x--;e[i].y--;

        mp[e[i].x][e[i].y]=mp[e[i].y][e[i].x]=1;

        out[e[i].x]++;

        out[e[i].y]++;

    }

    n--;

    for(int i=0;i<n;i++)

        for(int j=0;j<n;j++)

            if(mp[i][j])p[i][j]=1.0/out[j];

    for(int i=0;i<n;i++)

        p[i][i]-=1;

    p[0][n]=-1;

    gauss(n,p);

    for(int i=1;i<=m;i++)

        e[i].w=p[e[i].x][n]/out[e[i].x]+p[e[i].y][n]/out[e[i].y];

    sort(e+1,e+m+1,cmp);

    double ans=0;

    for(int i=1;i<=m;i++)

        ans+=e[i].w*i;

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

    return 0;

}

游走

BZOJ3141 Hnoi2013 游走 【概率DP】【高斯消元】*