BZOJ1415 [Noi2005]聪聪和可可
首先要预处理处当前聪聪在i点,可可在j点的时候聪聪下一步要走到哪里(这我都没想出来。。。
然后就比较简单了,根据套路,这个聪聪在x节点的期望应该是可可在j节点走到各种地方后,聪聪跟上的期望,当然也要算出可可留在原地,聪聪跑两步的期望。最后一加就好了。
一开始是这么想的,可害怕转移的东西互相依赖就没继续想了。。结果发现并不会相互依赖
#include<bits/stdc++.h>
const int N = 1020;
int n,e,cnt;
int c,m,last[N];
int st[N][N],pre[N],C[N],v[N];
int dis[N][N];
double f[N][N];
struct edge {
int to,next;
}E[N<<1];
inline int add(int x,int y){
cnt++;E[cnt].to=y,E[cnt].next=last[x],last[x]=cnt;
C[x]++;
}
inline int bfs(int s){
std::queue<int> q;
while(!q.empty()) q.pop();
q.push(s);
dis[s][s]=0;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=last[x];i;i=E[i].next){
if(E[i].to==x) continue;
if(dis[s][E[i].to]==-1||(dis[s][E[i].to]==dis[s][x]+1&&st[s][x]<st[s][E[i].to])){
dis[s][E[i].to]=dis[s][x]+1;
st[s][E[i].to]=st[s][x];
if(!st[s][x])st[s][E[i].to]=E[i].to;
q.push(E[i].to);
}
}
}
}
inline double find(int s,int x){//CC在S,KK在X的期望步数
if(f[s][x]) return f[s][x];
if(s==x) return 0;
if(st[s][x]==x||st[st[s][x]][x]==x) return f[s][x]=1;
double ans=find(st[st[s][x]][x],x);
for(int i=last[x];i;i=E[i].next){
ans+=1.0*find(st[st[s][x]][x],E[i].to);
}
return f[s][x]=ans/(C[x]+1)+1;
}
int main (){
scanf("%d %d",&n,&e);
scanf("%d %d",&c,&m);
for(int i=1;i<=e;++i){
int x,y;
scanf("%d %d",&x,&y);
add(x,y),add(y,x);
}
memset(dis,-1,sizeof(dis));
for(int i=1;i<=n;++i){
bfs(i);
}
double ans=find(c,m);
printf("%.3lf",ans);
return 0;
}
0 条评论