BZOJ 1415: [Noi2005]聪聪和可可(记忆化搜索+期望)

##解题思路
　　还是比较简答的一道题。首先$bfs$把每个点到其他点的最短路求出来，然后再记忆化搜索。记搜的时候猫的走法是确定的，搜一下老鼠走法就行了。

##代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<queue>

using namespace std;

const int MAXN = 1005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,m,head[MAXN],cnt,dis[MAXN][MAXN],to[MAXN<<1],nxt[MAXN<<1],S,T,du[MAXN];

double ans,f[MAXN][MAXN];

bool vis[MAXN];

queue<int> Q;

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

inline void bfs(int id){

	memset(vis,false,sizeof(vis));

	dis[id][id]=0;Q.push(id);vis[id]=1;int x,u;

	while(Q.size()){

		x=Q.front();Q.pop();

		for(int i=head[x];i;i=nxt[i]){

			u=to[i];if(vis[u]) continue;

			dis[id][u]=dis[id][x]+1;vis[u]=1;

			Q.push(u);

		}

	}

}

double dfs(int cat,int mouse){

	if(f[cat][mouse]!=0.0) return f[cat][mouse];

	int p=0;double sum=0;int prec=cat;

	for(int t=0;t<=1;t++){

		for(int i=head[cat];i;i=nxt[i]){

			int u=to[i];if(dis[mouse][u]>=dis[mouse][cat]) continue;

			if(!p || p>u) p=u;

		}

		if(p==mouse) return 1.0;cat=p;p=0;

	}

	if(cat==mouse) return 1.0;

	for(int i=head[mouse];i;i=nxt[i]){

		int u=to[i];

		if(u==cat) sum+=1.0/(double)(du[mouse]+1);

		else sum+=(double)(dfs(cat,u)+1.0)/(double)(du[mouse]+1);

	}sum+=(double)(dfs(cat,mouse)+1.0)/(double)(du[mouse]+1);

	return f[prec][mouse]=sum;

}

int main(){

	memset(dis,0x3f,sizeof(dis));

	n=rd(),m=rd();int x,y;S=rd();T=rd();

	for(int i=1;i<=m;i++){

		x=rd(),y=rd();

		add(x,y),add(y,x);du[x]++;du[y]++;

	}

	for(int i=1;i<=n;i++) bfs(i);

	printf("%.3lf",dfs(S,T));

	return 0;

}

巴特西

BZOJ 1415: [Noi2005]聪聪和可可(记忆化搜索+期望)

最新文章

热门文章