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

_预处理_ ： 根据题目要求聪聪会向可可不断靠近，且边无权，所以先进行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; } ```