[BZOJ1415][NOI2005]聪聪与可可

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

HINT

【样例说明1】
开始时，聪聪和可可分别在景点1和景点4。
第一个时刻，聪聪先走，她向更靠近可可(景点4)的景点走动，走到景点2，然后走到景点3；假定忽略走路所花时间。
可可后走，有两种可能：
第一种是走到景点3，这样聪聪和可可到达同一个景点，可可被吃掉，步数为1，概率为。
第二种是停在景点4，不被吃掉。概率为。
到第二个时刻，聪聪向更靠近可可(景点4)的景点走动，只需要走一步即和可可在同一景点。因此这种情况下聪聪会在两步吃掉可可。
所以平均的步数是1* +2* =1.5步。

对于所有的数据，1≤N,E≤1000。
对于50%的数据，1≤N≤50。

怎么办啊我太菜了这么简单的题都想不到...

首先用spfa预处理出nxt数组。

nxt[i, j]表示聪聪在i，可可在j，聪聪的下一步调到哪里。

我们对于每个点x都bfs一次，算出所有点到达它的最短路。

然后枚举点y，把x当做可可，y当做聪聪，然后枚举y的所有出边，这些边所到达的点是聪聪可以跳到的。

所以就记录一下最小的dis，如果有更小的dis就更新nxt[y, x]，如果有相同的dis，nxt[y, x]就和to取min...

这样处理出来nxt数组后，我们就可以毫无压力的进行dp；

设f[i, j]表示聪聪在i，可可在j，聪聪要吃掉可可的期望步数。

然后推一波公式...

$\LARGE f[i, j]=\frac{\sum_{to}^{ } f[nxt[nxt[i,j],j],to] + f[nxt[nxt[i,j],j],j]}{deg[j]+1} + 1$

然后如果聪聪可可在一个点上那么直接是0，如果nxt[nxt[i,j],j] = j 或者 nxt[i,j]=j那么直接f[i,j]=1；

这个可以用记忆化搜索实现...

我还是太菜了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

#define gc getchar()

inline int read(){

    int res=;char ch=gc;

    while(!isdigit(ch))ch=gc;

    while(isdigit(ch)){res=(res<<)+(res<<)+(ch^);ch=gc;}

    return res;

}

#undef gc

int n, m, c, e;

int nxt[][], dis[], deg[];

double f[][];

struct edge{

    int nxt, to;

}ed[];

int head[], cnt;

inline void add(int x, int y)

{

    ed[++cnt] = (edge){head[x], y};

    head[x] = cnt;

}

bool ex[];

inline void bfs(int cur)

{

    memset(dis, 0x3f, sizeof dis);

    memset(ex, , sizeof ex);

    dis[cur] = ;

    queue <int> q;

    q.push(cur);

    while(!q.empty())

    {

        int x = q.front();q.pop();

        ex[x] = ;

        int tmp = nxt[cur][x];

        for (int i = head[x] ; i ; i = ed[i].nxt)

        {

            int to = ed[i].to;

            if (dis[to] > dis[x] +  )

            {

                dis[to] = dis[x] + ;

                if (!ex[to]) ex[to] = , q.push(to);

            }

        }

    }

    for (int x =  ; x <= n ; x ++)

    {

        if (x == cur) continue;

        int mn = 1e9;

        for (int i = head[x] ; i ; i = ed[i].nxt)

        {

            int to = ed[i].to;

            if (dis[to] < mn) mn = dis[to], nxt[x][cur] = to;

            else if (dis[to] == mn) if (nxt[x][cur] > to) nxt[x][cur] = to;

        }

    }

}

double dp(int x, int y) //猫的位置x，鼠的位置y

{

    if (f[x][y]) return f[x][y];

    if (x == y) return ;

    if (nxt[nxt[x][y]][y] == y or nxt[x][y] == y) return f[x][y] = ;

    double sum = ;

    for (int i = head[y] ; i ; i = ed[i].nxt)

    {

        int to = ed[i].to;

        sum += dp(nxt[nxt[x][y]][y], to);

    }

    sum += dp(nxt[nxt[x][y]][y], y);

    return f[x][y] = sum / (deg[y] + ) + 1.0;

}

int main()

{

    n = read(), m = read(), c = read(), e = read();

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

    {

        int x = read(), y = read();

        add(x, y), add(y, x);

        deg[x]++, deg[y]++;

    }

    memset(dis, 0x3f, sizeof dis);

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

    printf("%.3lf\n", dp(c, e));

    return ;

}

巴特西