题意:给出n个点m条边的无向图,两个主角聪聪和可可开始分别在S点和T点。聪聪想吃掉可可,每次由匆匆先行动后来可可行动。聪聪的行动是选他到可可的最短路上的点走最多两步(如果最短路有几条就选编号最小的走),可可的行动是等概率选择一个出点或者不动。问聪聪吃掉可可的期望行动次数。

解法:这道题还是蛮有意思的。

首先我们必须得先注意到聪聪得行动是“智能”的不随机,这样我们不能计算的时候再考虑,我们必须得先预处理nxt[x][y]代表若聪聪在x点可可在y点下一步聪聪会走那个点(根据定义就是x到y最短路的编号最小点)预处理这个我们可以做n次最短路,方法是:当在x点能更新到某个点y的最短路的时候,随便把这个nxt[st][y]与nxt[st][x]取一个最小值。

预处理之后我们就可以开始计算答案了。

因为在图上dp,没有比较显然的阶段所以我们使用记忆化搜素。dp[x][y]代表聪聪在x点,可可在y点的期望答案。分3种情况转移:

①x==y  , dp[x][y]=0

②x能通过1/2步走到y,dp[x][y]=1

③否则  to=x向y走两步走到的点,dp[x][y]=(sigma(dp[to][z])+dp[to][y]) / (du[y]+1) + 1 ;   (z表示y出点,du[y]表示y出度),应该比较好理解就是聪聪先走两部,然后可可随机走一步(或者停)的期望相加。

这里提一点,为什么在这个图上能走dp,dp状态之间不会有环吗?因为其实聪聪的行动是十分“智能”的,这就导致了dp状态之间其实不会有环,会有先后顺序。

代码如下:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e3+10;
 4 const int INF=0x3f3f3f3f;
 5 int n,m,s,t;
 6 vector<int> G[N];
 7 double dp[N][N];
 8 bool vis[N][N];
 9
10 int nxt[N][N];
11 queue<int> q;
12 int dis[N]; bool inq[N];
13 void spfa(int st) {
14     for (int i=1;i<=n;i++) dis[i]=INF,inq[i]=0;
15     dis[st]=0;
16     for (int i=0;i<G[st].size();i++) {
17         int y=G[st][i];
18         dis[y]=1; q.push(y); inq[y]=1;
19         nxt[st][y]=min(nxt[st][y],y);
20     }
21     while (!q.empty()) {
22         int x=q.front(); q.pop();
23         for (int i=0;i<G[x].size();i++) {
24             int y=G[x][i];
25             if (dis[y]>=dis[x]+1) {
26                 dis[y]=dis[x]+1;
27                 nxt[st][y]=min(nxt[st][y],nxt[st][x]);
28                 if (!inq[y]) q.push(y),inq[y]=1;
29             }
30         }
31         inq[x]=0;
32     }
33 }
34
35 double dfs(int s,int t) {
36     if (vis[s][t]) return dp[s][t];
37     int to=nxt[nxt[s][t]][t];
38     vis[s][t]=1;
39     if (s==t) return dp[s][t]=0.0;
40     if (to==t) return dp[s][t]=1.0;
41     dp[s][t]+=dfs(to,t);
42     for (int i=0;i<G[t].size();i++)
43         dp[s][t]+=dfs(to,G[t][i]);
44     dp[s][t]/=(double)(G[t].size()+1);
45     dp[s][t]+=1.0;
46     return dp[s][t];
47 }
48
49 int main()
50 {
51     cin>>n>>m>>s>>t;
52     for (int i=1;i<=m;i++) {
53         int x,y; scanf("%d%d",&x,&y);
54         G[x].push_back(y);
55         G[y].push_back(x);
56     }
57
58     memset(nxt,0x3f,sizeof(nxt));
59     for (int i=1;i<=n;i++) nxt[i][i]=i;
60     for (int i=1;i<=n;i++) spfa(i);
61
62     memset(dp,0,sizeof(dp));
63     memset(vis,0,sizeof(vis));
64     printf("%.3lf\n",dfs(s,t));
65     return 0;
66 }
01-19 03:37