本文共 2269 字，大约阅读时间需要 7 分钟。
我们可以用n次BFS预处理出 to[][]数组，to[i][j]表示聪聪从i点到j点第一步会走哪个点。
那么对于聪聪在i点，可可在j点，聪聪先走，定义dp[i][j]表示步数期望。
那么显然有dp[i][j]=(sigma(dp[p][w])+dp[p][j])/(dee[j]+1)+1.
其中p表示to[to[i][j]][j],w表示j点邻接的点。
边界状态就是 如果i==j，那么dp[i][j]=0. 如果i和j的距离在聪聪的一步之内，那么dp[i][j]=1.
记忆化搜索一下即可。
# include # include # include # include # include # include # include # include # include # include # include using namespace std;# define lowbit(x) ((x)&(-x))# define pi 3.1415926535# define eps 1e-9# define MOD 100000007# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i PII;typedef vector VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=1005;//Code begin...struct Edge{ int p, next;}edge[N<<1];int to[N][N], f[N], dee[N], head[N], cnt=1, n, vis[N];double dp[N][N];bool mark[N][N];queue Q;void add_edge(int u, int v){ edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;}void bfs(){ FOR(i,1,n) { mem(vis,0); mem(f,0); Q.push(i); vis[i]=1; while (!Q.empty()) { int v=Q.front(); Q.pop(); for (int j=head[v]; j; j=edge[j].next) { int u=edge[j].p; if (vis[u]) { if (vis[v]==vis[u]-1) f[u]=min(f[u],f[v]); continue; } Q.push(u); vis[u]=vis[v]+1; if (vis[u]<=2) f[u]=u; else f[u]=f[v]; } } FOR(j,1,n) to[i][j]=f[j]; }}double dfs(int x, int y){ if (mark[x][y]) return dp[x][y]; mark[x][y]=1; if (x==y) return dp[x][y]=0; if (to[x][y]==y||to[to[x][y]][y]==y) return dp[x][y]=1; int p=to[to[x][y]][y]; double res=dfs(p,y); for (int i=head[y]; i; i=edge[i].next) res+=dfs(p,edge[i].p); res=res/(dee[y]+1)+1; return dp[x][y]=res;}int main (){ int m, u, v, s, t; scanf("%d%d",&n,&m); scanf("%d%d",&s,&t); while (m--) scanf("%d%d",&u,&v), add_edge(u,v), add_edge(v,u), ++dee[v], ++dee[u]; bfs(); printf("%.3f\n",dfs(s,t));}
转载于:https://www.cnblogs.com/lishiyao/p/6567880.html
