传送门
解题思路
还是比较简答的一道题. 首先 \(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;
- }
来源: http://www.bubuko.com/infodetail-2867576.html