【bzoj1415】[Noi2005]聪聪和可可

2015.04.15 16:28 Wed | 2次阅读 | 旧日oi | 固定链接 | 源码

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。

题解

数学期望
我们可以用n^2的时间处理出当猫在x,鼠在y时猫下一步要走的路,记为p[x][y]
之后我们可以以a,b为起点进行dp。
设ex[x][y]为猫在x,鼠在y时的期望步数
则显然当p[x][y]=y||p[p[x][y]][y]=y时ex[x][y]=1
其他情况下ex[x][y]=sigma(ex[p[p[x][y]][y],k)/(outdegree[y])+1,k为y自己或和y相邻的点

我的程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,cnt,a,b;
int d[1001];
int dis[1001][1001],p[1001][1001];
double f[1001][1001];
struct edge{
    int to,next;
}e[1001];
int h[1001],tp;
queue<int> q;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;d[u]++;
}
double dp(int x,int y)
{
    if(f[x][y])return f[x][y];
    if(x==y)return 0;
    if(p[x][y]==y||p[p[x][y]][y]==y)return f[x][y]=1;
    double tot=dp(p[p[x][y]][y],y);
    for(int i=h[y];i;i=e[i].next)
        tot+=dp(p[p[x][y]][y],e[i].to);
    return f[x][y]=tot/(d[y]+1)+1;
}
void bfs(int x)
{
    int t=0,w=1;
    q.push(x);
    dis[x][x]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        int tmp=p[x][now];
        for(int i=h[now];i;i=e[i].next)
            if(dis[x][e[i].to]==-1||(1+dis[x][now]==dis[x][e[i].to]&&tmp<p[x][e[i].to]))
            {
                dis[x][e[i].to]=dis[x][now]+1;
                p[x][e[i].to]=tmp;
                if(!tmp)p[x][e[i].to]=e[i].to;
                q.push(e[i].to);
            }
    }
}
int main()
{
    memset(dis,-1,sizeof(dis));
    scanf("%d%d",&n,&m);
    scanf("%d%d",&a,&b);
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        ae(u,v);
        ae(v,u);
    }
    for(int i=1;i<=n;i++)bfs(i);
    printf("%.3lf",dp(a,b));
    return 0;
}```