题解 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;
}
```