题解 P4206 【[NOI2005]聪聪与可可 】

2018-04-24 14:17:00


预处理 : 根据题目要求聪聪会向可可不断靠近,且边无权,所以先进行N次广度优先搜索,预处理出p[i, j]表示顶点i到顶点j的最短路上与顶点i相邻且编号最小的顶点编号。即聪聪在景点i,可可在景点j时,聪聪第1步会走到的景点编号。 设f [i, j]来表示聪聪在顶点i,可可在顶点j时聪聪抓住可可的平均步数。令w[i, j]表示与顶点i相邻的j个点编号,而用t[i]表示顶点i的度


思路 : 可以确定聪聪下一步所在的顶点即p[p[i, j], j],可可下一步在顶点w[i, j],概率为1/(1+t[j]),下一步这个情况下的期望f [p[p[i, j], j], w[i, j]]已经计算出,那么就是比f [p[p[i, j], j], w[i, j]]多出一步。可可在原地停留的情况则类似。 当然,f [i, i] = 0,因为聪聪和可可已经在同一个点。若p[p[i, j], j] = j 或p[i, j] = j 则说明在这一时间单位内聪聪即可吃掉可可,那么f [i, j]=1。 用记忆化搜索即可解决 c++AC代码

#include<iostream>
#include<cstring>
#include<math.h>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
int p[1010][1010];//聪聪在i可可在j,聪聪下一步会到达的点为p[i][j] 
double f[1005][1005];//聪聪在i可可在j,抓到步数的期望
int w[1010][1010];
int t[1010];//每个点的度 
int n,e,c,m;
int dist[1010][1010];
int inque[1010];
queue <int > q;
struct Node{
    int v;
    int next;
}node[2010];
int top=0;
int head[1010];
void addedge(int u,int v){
    node[++top].v=v;
    node[top].next=head[u];
    head[u]=top;
}
void spfa(int s) {
    memset(dist[s],0x3f,sizeof(dist[s]));
    dist[s][s]=0;
    int i;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(i=head[u];i;i=node[i].next) {
            if(dist[s][node[i].v]>dist[s][u]+1) {
                dist[s][node[i].v]=dist[s][u]+1;
                if(inque[node[i].v]==0) {
                    inque[node[i].v]=1;
                    q.push(node[i].v);
                }
            }
        }
    }
}
double dfs(int i,int j) {
    if(f[i][j]!=0) {
        return f[i][j];
    }
    if(i==j)return f[i][j]=0.0;
    if(p[p[i][j]][j]==j)return f[i][j]=1.0;
    if(p[i][j]==j)return f[i][j]=1.0;
    for(int k=1; k<=t[j]; k++) {
        f[i][j]+=dfs(p[p[i][j]][j],w[j][k]);//可可乱走的所有情况 
    }
    f[i][j]=(f[i][j]+dfs(p[p[i][j]][j],j))/(double)(t[j]+1)+1;//停留在原地的情况,除以概率,加上本步所用的时间 
    return f[i][j];
}
int main() {
    scanf("%d%d%d%d",&n,&e,&c,&m);
    int i,j,a,b;
    for(i=1; i<=e; i++) {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
        t[a]++;
        t[b]++;
        w[a][t[a]]=b;
        w[b][t[b]]=a;
    }
    int k;
    for(i=1; i<=n; i++) p[i][i]=0, spfa(i);//求出任意两点间的距离 
    memset(p,0x7f,sizeof(p));
    for(i=1; i<=n; i++) {
        for(j=1; j<=t[i]; j++) {
            for(k=1; k<=n; k++) {
                if(dist[i][k]==dist[w[i][j]][k]+1&&p[i][k]>w[i][j]) {
                    p[i][k]=w[i][j];
                }
            }
        }
    }
    printf("%.3lf",dfs(c,m));
    return 0;
}