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

题面

题解

先预处理出当可可在某个点，聪聪在某个点时

聪聪会往哪里走

然后记忆化搜索一下就好了

#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;

}

巴特西

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

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

题面

题解

最新文章

热门文章