BZOJ 1415 [Noi2005] 聪聪和可可概率DP

Description#

Input#

数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

Output#

输出1个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

Sample Input#

【输入样例1】
4 3
1 4
1 2
2 3
3 4
【输入样例2】
9 9
9 3
1 2
2 3
3 4
4 5
3 6
4 6
4 7
7 8
8 9

Sample Output#

【输出样例1】
1.500
【输出样例2】
2.167

题解#

先每个点跑一遍SPFA
求出p[i][j]表示当可可在 j 点时，聪聪在 i 点要走的下一步
然后记忆化搜索
$f[s][e]=\sum_{tmp=p[p[i][e]][e],e->j}{\frac{f[tmp][j]}{du[e]+1}}$

1
#include<cstdio>
2
#include<cstring>
3
#include<algorithm>
4
#include<queue>
5
using namespace std;
6
struct edge{
7
    int END,next;
8
}v[100005];
9
int first[1005],Index,du[1005],n;
10
void add(int a,int b){
11
    du[a]++;
12
    v[Index].END=b;
13
    v[Index].next=first[a];
14
    first[a]=Index++;
15
}
16
int p[1005][1005];
17
double f[1005][1005];
18
void spfa(int x){
19
    queue<int> Q;
20
    bool flag[1005]={0};
21
    int dis[1005],fr[1005];
22
    memset(dis,0x3f,sizeof(dis));
23
    memset(fr,0,sizeof(fr));
24
    dis[x]=0;
25
    flag[x]=1;Q.push(x);
26
    while(!Q.empty()){
27
        int k=Q.front();
28
        Q.pop();flag[k]=0;
29
        for(int i=first[k];i!=-1;i=v[i].next){
30
            if(dis[v[i].END]>dis[k]+1||(dis[v[i].END]==dis[k]+1&&k<fr[v[i].END])){
31
                dis[v[i].END]=dis[k]+1;
32
                fr[v[i].END]=k;
33
                if(!flag[v[i].END]){
34
                    flag[v[i].END]=1;
35
                    Q.push(v[i].END);
36
                }
37
            }
38
        }
39
    }
40
    for(int i=1;i<=n;i++)
41
        if(i!=x)
42
            p[i][x]=fr[i];
43
}
44
double dfs(int s,int e){
45
    if(s==e)return f[s][e]=0;
46
    if(p[s][e]==e||p[p[s][e]][e]==e)return f[s][e]=1;
47
    if(f[s][e]<=1e9) return f[s][e];
48
    int tmp=p[p[s][e]][e];
49
    f[s][e]=1;
50
    for(int i=first[e];i!=-1;i=v[i].next){
51
        f[s][e]+=dfs(tmp,v[i].END)/(du[e]+1);
52
    }
53
    f[s][e]+=dfs(tmp,e)/(du[e]+1);
54
    return f[s][e];
55
}
56
int main()
57
{
58
    //freopen("cchkk.in","r",stdin);
59
  //freopen("cchkk.out","w",stdout);
60
    memset(first,-1,sizeof(first));
61
    memset(f,0x7f,sizeof(f));
62
    int m,s,e,a,b;
63
    scanf("%d%d%d%d",&n,&m,&s,&e);
64
    for(int i=1;i<=m;i++){
65
        scanf("%d%d",&a,&b);
66
        add(a,b);
67
        add(b,a);
68
    }
69
    for(int i=1;i<=n;i++)
70
        spfa(i);
71
    printf("%.3lf",dfs(s,e));
72
    //while(1);
73
}