NOI2005 聪聪与可可

wjh15101051's space

卧薪尝胆，厚积薄发。

NOI2005 聪聪与可可

Date: Thu Sep 06 17:20:07 CST 2018

In Category: NoCategory

Description：

给定一个无向图，聪聪在起点，可可在终点，每个时刻聪聪会沿最短路走向可可两步(如果有多条最短路走编号最小的点)，然后可可会等概率向周围走或不动，求平均多少个时刻后聪聪和可可相遇。

$1\le n \le 1000$

Solution：

注意到无论着他们怎么走，聪聪和可可之间的距离永远会越来越近，所以这个问题具有天生的阶段性质。

预处理 $w[i][j]$ 表示聪聪在 $i$ ，可可在 $j$ ，聪聪下一步走到的位置，每个点做 $SPFA$ 记一个前驱即可求出。

设 $f[i][j]$ 表示聪聪在 $i$ ，可可在 $j$ 相遇的期望，暴力枚举可可的移动记忆化搜索就能过。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

int s,t;

#define MAXN 1010

#define MAXM 1010

int ind[MAXN];

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++ind[a];++ind[b];

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int w[MAXN][MAXN],d[MAXN][MAXN];

bool v[MAXN];

int fr[MAXN];

double f[MAXN][MAXN];

bool vis[MAXN][MAXN];

double dp(int a,int b)

{

	if(a == b)return 0;

	if(w[a][b] == b)return 1;

	if(w[w[a][b]][b] == b)return 1;

	if(vis[a][b])return f[a][b];

	int p = w[w[a][b]][b];

	double res = 0;

	for(int i = lin[b];i != 0;i = e[i].nxt)

		res += dp(p,e[i].to) + 1;

	res += dp(p,b) + 1;

	res = res / (ind[b] + 1);

	vis[a][b] = true;f[a][b] = res;

	return res;

}

int main()

{

	memset(vis,false,sizeof(vis));

	scanf("%d%d",&n,&m);

	scanf("%d%d",&s,&t);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	for(int x = 1;x <= n;++x)

	{

		queue<int> q;

		q.push(x);

		memset(d[x],0x3f,sizeof(d[x]));

		d[x][x] = 0;

		memset(fr,0x3f,sizeof(fr));

		while(!q.empty())

		{

			int k = q.front();q.pop();

			v[k] = false;

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(d[x][e[i].to] > d[x][k] + 1 || (d[x][e[i].to] == d[x][k] + 1 && k < fr[e[i].to]))

				{

					d[x][e[i].to] = d[x][k] + 1;

					fr[e[i].to] = k;

					if(!v[e[i].to])

					{

						q.push(e[i].to);

					}

				}

			} 

		}

		for(int i = 1;i <= n;++i)

			if(i != x)

				w[i][x] = fr[i];

	}

	printf("%.3lf\n",dp(s,t));

	return 0;

}

In tag: DP-记忆化搜索数学-概率与期望

wjh15101051