无向简单图上给定s，t。每秒s先向t按照最短路走两步(优先节点编号较小的)，然后t随机行动一步。
问期望多少秒相遇。n <= 1000
解：
这个s太蛇皮了...所以预处理一波。
然后不会，看题解发现是SB记忆化搜索......
#include <bits/stdc++.h> const int N = ;
const double eps = 1e-; struct Edge {
int nex, v;
}edge[N << ]; int tp; int e[N], gt[N][N], n, m, fr[N], d[N], vis[N], in[N], frfr[N];
double f[N][N];
std::queue<int> Q; inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} void DFS(int x, int s) {
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(fr[y] == x) {
gt[s][y] = gt[s][x];
DFS(y, s);
}
}
return;
} inline void BFS(int s) {
Q.push(s);
vis[s] = s;
d[s] = ;
fr[s] = ; frfr[s] = ;
while(Q.size()) {
int x = Q.front();
Q.pop();
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(vis[y] != s) {
vis[y] = s;
d[y] = d[x] + ;
fr[y] = x;
frfr[y] = (x == s) ? y : frfr[x];
Q.push(y);
}
else if(d[y] == d[x] + ) {
if(frfr[x] < frfr[y]) {
frfr[y] = frfr[x];
fr[y] = x;
}
}
}
}
/// get gt
gt[s][s] = s; f[s][s] = ;
for(int i = e[s]; i; i = edge[i].nex) {
int y = edge[i].v;
gt[s][y] = y;
DFS(y, s);
}
return;
} double F(int x, int y) {
if(f[x][y] >= -eps) {
return f[x][y];
}
if(gt[x][y] == y || gt[gt[x][y]][y] == y) {
return f[x][y] = ;
}
double ans = ; int z = gt[gt[x][y]][y];
for(int i = e[y]; i; i = edge[i].nex) {
int w = edge[i].v;
ans += F(z, w);
}
ans += F(z, y); return f[x][y] = ans / (in[y] + ) + ;
} int main() {
int s, t;
scanf("%d%d", &n, &m);
scanf("%d%d", &s, &t);
for(int i = , x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
in[x]++; in[y]++;
} for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
f[i][j] = -;
}
} for(int i = ; i <= n; i++) {
BFS(i);
} /*printf("-----------\n");
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
printf("%d ", gt[i][j]);
}
printf("\n");
}
printf("-----------\n");
*/ printf("%.3f\n", F(s, t));
return ;
}
AC代码
感觉不会死循环的原因是每次之后s和t的距离至少减少1，至多减少3。按s和t的距离分层的话每一步都走到了不同的层。