BZOJ1415 [NOI 2005] 聪聪与可可 -概率与期望

题目链接

大致思路

期望题的话，比较容易看出可以用记搜解决。由于每次走的时候要考虑一个距离问题，所以可以预处理出来dis[i][j]表示任意两点间的距离。因为数据范围比较小而且边权均为1，所以可以直接用bfs解决（暴力档弗洛伊德写挂导致少了40分，真实自闭了）。
这里是每次直接考虑走两步，如果走第一步的时候已经到达就返回1，否则就继续往下走第二步。

#include<bits/stdc++.h>
#define M 1005
#define db double
using namespace std;
bool cur1;
int pr[M<<1],to[M<<1],la[M],n,m,tot,S,T,sz[M];
void add(int x,int y) {
	to[++tot]=y,pr[tot]=la[x],la[x]=tot;
}
int dis[M][M];
db dp[M][M];
bool mark[M][M];
db dfs(int x,int y) {
	if(x==y)return 0;//已经到达了同一个点，可以直接返回
	if(mark[x][y])return dp[x][y];//记搜
	mark[x][y]=1;
	int Mi=1e9,pos=n+1;
	for(int i=la[x]; i; i=pr[i]) {
		int Y=to[i];
		if(dis[Y][y]<Mi||dis[Y][y]==Mi&&Y<pos)pos=Y,Mi=dis[Y][y];//找到下一步走的点，注意相同的时候找标号较小的点
	}
	if(pos==y)return dp[x][y]=1.0;
	db res=1.0;
	if(pos!=y) {
		int now=pos;
		Mi=1e9,pos=n+1;
		for(int i=la[now]; i; i=pr[i]) {
			int Y=to[i];
			if(dis[Y][y]<Mi||dis[Y][y]==Mi&&Y<pos)pos=Y,Mi=dis[Y][y];
		}
		if(pos==y)return dp[x][y]=1.0;
		db k=1.0/(sz[y]+1);//选每个点的概率
		for(int i=la[y]; i; i=pr[i]) {
			int z=to[i];
			res+=dfs(pos,z)*k;
		}
		res+=dfs(pos,y)*k;
	}
	return dp[x][y]=res;
}
bool cur2;
struct P2 {
	queue<int>Q;
	bool vis[M];
	void bfs(int s,int *Dis) {
		while(!Q.empty())Q.pop();
		Q.push(s);
		memset(vis,0,sizeof(vis));
		Dis[s]=0,vis[s]=1;
		while(!Q.empty()) {
			int x=Q.front();
			Q.pop();
			for(int i=la[x]; i; i=pr[i]) {
				int y=to[i];
				if(vis[y])continue;
				Dis[y]=Dis[x]+1;
				vis[y]=1,Q.push(y);
			}
		}
	}
	void solve() {
		for(int i=1; i<=n; i++)bfs(i,dis[i]);
		memset(mark,0,sizeof(mark));
		printf("%.3f
",dfs(S,T));
	}
} p2;
int main() {
//	printf("%lf
",(&cur2-&cur1)/1024.0/1024);
	freopen("cchkk.in","r",stdin);
	freopen("cchkk.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&S,&T);
	for(int i=1; i<=m; i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		sz[x]++,sz[y]++;
		add(x,y),add(y,x);
	}
	p2.solve();
	return 0;
}