由于可以求出当老鼠在j点，猫在i点时猫的下一步决策next[i][j]，于是就是水水的期望Dp了。
f[i][j]代表猫在i,老鼠在j时期望几步捉到老鼠。
f[i][j] = (f[next[next[i][j]][j]][j] + ∑(f[next[next[i][j]][j]][v]){(i,v)∈E})/(ind[j] + 1) + 1
View Code
/************************************************************** Problem: 1415 User: lazycal Language: C++ Result: Accepted Time:148 ms Memory:12800 kb ****************************************************************/ #include <cstdio> #include <queue> const int N = 1000 + 9; double f[N][N]; int next[N][N],son[N],n,m,e,c,ind[N],ec; struct Edge{int link,next;}es[N*2]; inline void addedge(const int x,const int y) { es[++ec].link = y; es[ec].next = son[x]; son[x] = ec; } inline void Addedge(const int x,const int y) {addedge(x,y);addedge(y,x);} void bfs(const int s) { static std::queue<int> q; static int vis[N],time,dis[N]; ++time; dis[s] = 0; for (vis[s] = time,q.push(s); !q.empty(); q.pop()) { const int u = q.front(); for (int i = son[u]; i; i = es[i].next) { const int v = es[i].link; if (vis[v] == time) { if (dis[v] == dis[u] + 1 && next[s][v] > next[s][u]) next[s][v] = next[s][u]; continue; } if (u != s) next[s][v] = next[s][u]; else next[s][v] = v; vis[v] = time; dis[v] = dis[u] + 1; q.push(v); } } } double dp(const int x,const int y) { if (f[x][y] != -1) return f[x][y]; if (x == y) return f[x][y] = 0; if (next[x][y] == y || next[next[x][y]][y] == y) return f[x][y] = 1; f[x][y] = dp(next[next[x][y]][y],y); for (int i = son[y]; i; i = es[i].next) f[x][y] += dp(next[next[x][y]][y],es[i].link); return (f[x][y] /= ind[y] + 1) += 1; } int main() { #ifndef ONLINE_JUDGE freopen("1415.in","r",stdin); freopen("1415.out","w",stdout); #endif scanf("%d%d%d%d",&n,&e,&c,&m); for (int x,y;e--;) scanf("%d%d",&x,&y),Addedge(x,y),++ind[x],++ind[y]; for (int i = 1; i <= n; ++i) bfs(i); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) f[i][j] = -1.0; printf("%.3f\n",dp(c,m)); }
转载于:https://www.cnblogs.com/lazycal/p/3264605.html
