[Hnoi2013]游走

发表于 | 分类于

题目

一个无向连通图，顶点从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

OUTPUT

3.333

解题报告

这东西显然是个概率与期望（题目写的那么清楚啊喂），好吧，是一个很裸的概率与期望。
题目要求总分最小，且编号从1到m，那么显然，我们需要求一下每条边被经过的期望，期望越大，编号越小。
首先自然能删除终点的所有出边（终点是不能出来的），然后，对于每一条边，设两端端点为u，v，我们可以从u走到v，也可以从v走到u，从u走到v的期望次数等于

经过点u的次数/u的度

问题自然就转化成求每个点的期望经过次数，对于起点来说，一开始一定会经过一次，在之后也可能被经过。

f[1]=1+sigma(f[j]/degree[j],j和1有边相连)

f[i]=sigma(f[j]/degree[j],i与j有边相连)

我们得到了n变量n方程的方程组，然后高斯消元乱抡= =
稍微处理下就可以得到经过每个点的期望，那么每条边的期望即为两端点期望之和（注意：对终点一定要特殊处理啊啊啊），对每条边按期望排序，随便一乘，一加，就可以AC了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
struct edge{
    int s,e,n;
}ed[250001];
int pre[501],tot;
inline void insert(int s,int e){
    ed[++tot].s=s;
    ed[tot].e=e;
    ed[tot].n=pre[s];
    pre[s]=tot;
}
int du[501];
int n,m;
double a[501][501],b[501],ans[501];
inline double jdz(double x){
    return x>=0?x:-x;
}
inline void swp(double &a,double &b){
    double c(a);
    a=b;
    b=c;
}
inline void gauss(){
    int num,cnt(1);
    for(int i=1;i<n;i++,cnt++){
        num=i;
        for(int j=i+1;j<=n;j++)
            if(jdz(a[num][i])<jdz(a[j][i]))
                num=j;
        if(num!=i){
            for(int j=1;j<=n;j++)
                swp(a[num][j],a[cnt][j]);
            swp(b[num],b[cnt]);
        }
        if(!a[cnt][i]){
            cnt--;
            continue;
        }
        for(int j=cnt+1;j<=n;j++){
            double t(a[j][i]/a[cnt][i]);
            for(int k=i;k<=n;k++)
                a[j][k]-=t*a[i][k];
            b[j]-=t*b[i];
        }
    }
    for(int i=n;i>0;i--){
        for(int j=n;j>i;j--)
            b[i]-=a[i][j]*ans[j];
        ans[i]=b[i]/a[i][i];
    }
}
double f[250001];
bool g[501][501];
inline int gg(){
//  freopen("walk.in","r",stdin);
//  freopen("walk.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x(read()),y(read());
        insert(x,y);
        g[x][y]=g[y][x]=1;
        du[x]++,du[y]++;
    }
    du[n]=0;
    for(int i=1;i<=n;i++){
        if(i==1)
            b[i]=1;
        else
            b[i]=0;
        for(int j=1;j<=n;j++){
            if(i==j){
                a[i][j]=1;
                continue;
            }
            if(j==n){
                a[i][j]=0;
                continue;
            }
            if(g[i][j])
                a[i][j]=-1.0/(double)du[j];
        }
    }
    gauss();
    for(int i=1;i<n;i++)
        ans[i]/=du[i];
    ans[n]=0;
    for(int i=1;i<=tot;i++){
        int s(ed[i].s),e(ed[i].e);
        f[i]=ans[s]+ans[e];
    }
    int cnt(tot);
    sort(f+1,f+tot+1);
    double an(0);
    for(int i=1;i<=tot;i++)
        an+=i*f[cnt--];
    printf("%.3lf",an);
    return 0;
}
int k(gg());
int main(){;}

ps:COGS rk1代码奉上，虽然榜貌似被两个神奇的（hhh）刷成（hhh）了，但是还是没有什么影响。