BZOJ 3143 [Hnoi2013]游走高斯消元概率DP

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

题解#

用贪心的思想
要使期望最小那么可以先求出每条边的期望经过次数
然后问题就转化成了求每条边的期望经过次数
可能从u走到v,也可能从v走到u,从u走到v的期望次数等于经过点u的次数/u的度数
这样就转化成了每个点的期望经过次数
易得
$f[1]=1+\sum_{j!=n}{f[j]/degree(j)}$
$f[i]=\sum_{j!=n}{f[j]/degree(j)} (i!=n)$

这样就建立了一个n-1元方程组

高斯消元解就可以了

代码比较丑

1
#include<cstring>
2
#include<cstdio>
3
#include<algorithm>
4
#include<cmath>
5
using namespace std;
6
struct edge{
7
    int END,next;
8
}v[500005];
9
int first[505],p,du[505];
10
void add(int a,int b){
11
    v[p].END=b;
12
    v[p].next=first[a];
13
    first[a]=p++;
14
}
15
template<typename T>
16
int cmp(const T a,const T b){
17
    return a > b;
18
}
19
double a[505][505],x[505],f[500005];
20
int n,m;
21
void gauss(){
22
    int im,num=1;
23
    for(int k=1;k<=n;k++,num++){
24
        im=k;
25
        for(int i=k+1;i<=n;i++)
26
            if(fabs(a[i][k])>fabs(a[im][k]))
27
                im=i;
28
        if(im!=k){
29
            for(int i=k;i<=n+1;i++)
30
                swap(a[num][i],a[im][i]);
31
        }
32
        if(!a[num][k]){
33
            num--;continue;
34
        }
35
        for(int i=num+1;i<=n;i++){
36
            if(!a[num][i])continue;
37
            double t=a[i][k]/a[num][k];
38
            for(int j=k;j<=n+1;j++){
39
                a[i][j]-=t*a[k][j];
40
            }
41
        }
42
    }
43
    for(int i=n;i>=1;i--){
44
        for(int j=n;j>=i+1;j--){
45
            a[i][n+1]-=a[i][j]*x[j];
46
        }
47
        x[i]=a[i][n+1]/a[i][i];
48
    }
49
}
50
int main()
51
{
52
    //freopen("walk.in","r",stdin);
53
  //freopen("walk.out","w",stdout);
54
    memset(first,-1,sizeof(first));
55
    scanf("%d%d",&n,&m);
56
    int s,e;
57
    for(int i=1;i<=m;i++){
58
        scanf("%d%d",&s,&e);
59
        du[s]++;du[e]++;
60
        add(s,e);add(e,s);
61
    }
62
    n--;
63
    a[1][n+1]=-1;
64
    for(int i=1;i<=n;i++){
65
        a[i][i]=-1;
66
        for(int j=first[i];j!=-1;j=v[j].next){
67
            if(v[j].END!=n+1)
68
                a[i][v[j].END]+=(double)1/(du[v[j].END]);
69
        }
70
    }
71
    gauss();
72
    for(int i=0;i<p;i++){
73
        //if(v[i].END!=n+1)
74
            f[i>>1]+=x[v[i].END]/du[v[i].END];
75
    }
76
    //for(int i=0;i<m;i++){
77
    //    printf("%lf\n",f[i+1]);
78
    //}
79
    //while(1);
80
    sort(f,f+m,cmp<double>);
81
    double ans=0;
82
    for(int i=0;i<m;i++){
83
        ans+=f[i]*(i+1);
84
    }
85
    printf("%.3lf",ans);
86
    //while(1);
87
}