【BZOJ1415】【NOI2005】聪聪和可可（动态规划，数学期望）

题面

BZOJ

题解

先预处理出当可可在某个点，聪聪在某个点时
聪聪会往哪里走
然后记忆化搜索一下就好了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 1111
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1,iv[MAX];
int p[MAX][MAX],dis[MAX];
bool vis[MAX];
int n,m;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;iv[u]++;}
void BFS(int S)
{
	queue<int> Q;Q.push(S);
	memset(vis,0,sizeof(vis));
	vis[S]=true;dis[S]=0;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=h[u];i;i=e[i].next)
		{
			if(vis[e[i].v])continue;
			vis[e[i].v]=true;
			dis[e[i].v]=dis[u]+1;
			Q.push(e[i].v);
		}
	}
}
void Pre(int S)
{
	BFS(S);dis[0]=1e9;
	for(int u=1;u<=n;++u)
		for(int i=h[u];i;i=e[i].next)
			if(dis[p[u][S]]>dis[e[i].v]||(dis[p[u][S]]==dis[e[i].v]&&e[i].v<p[u][S]))
				p[u][S]=e[i].v;
	p[S][S]=S;
}
int S,T;
double f[MAX][MAX];
double DFS(int u,int v)
{
	if(f[u][v]!=-1.0)return f[u][v];
	if(u==v)return f[u][v]=0;
	if(p[u][v]==v)return f[u][v]=1.0;
	if(p[p[u][v]][v]==v)return f[u][v]=1.0;
	f[u][v]=0;
	for(int i=h[v];i;i=e[i].next)
		f[u][v]+=DFS(p[p[u][v]][v],e[i].v);
	f[u][v]+=DFS(p[p[u][v]][v],v);
	f[u][v]/=(iv[v]+1);f[u][v]+=1;
	return f[u][v];
}
int main()
{
	n=read();m=read();
	S=read();T=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		Add(u,v);Add(v,u);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			f[i][j]=-1;
	for(int i=1;i<=n;++i)Pre(i);
	printf("%.3lf\n",DFS(S,T));
	return 0;
}