bzoj 1415: [Noi2005]聪聪和可可【期望dp+bfs】

因为边权为1所以a直接bfs瞎搞就行……我一开始竟然写了个spfa

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int N=1005,inf=1e9;

int n,m,st,ed,h[N],cnt,a[N][N],b[N][N],dis[N][N],d[N];

double f[N][N];

bool v[N][N];

struct qwe

{

	int ne,to;

}e[N<<1];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

double dfs(int u,int v)

{

	if(f[u][v]>=-1)

		return f[u][v];

	if(u==v)

		return f[u][v]=0;

	if(dis[u][v]<=2)

		return f[u][v]=1;

	double p=1.0/((double)d[v]+1.0);

	f[u][v]=1;

	for(int i=h[v];i;i=e[i].ne)

		f[u][v]+=p*dfs(a[u][v],e[i].to);

	f[u][v]+=p*dfs(a[u][v],v);

	return f[u][v];

}

int main()

{

	n=read(),m=read(),st=read(),ed=read();

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

	{

		int x=read(),y=read();

		d[x]++,d[y]++;

		add(x,y),add(y,x);

	}

	queue<int>q;

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

	{

		v[s][s]=1;

		q.push(s);

		while(!q.empty())

		{

			int u=q.front();

			q.pop();

			for(int i=h[u];i;i=e[i].ne)

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

				{

					dis[s][e[i].to]=dis[s][u]+1;

					v[s][e[i].to]=1;

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

				}

		}

	}

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

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

		{

			int mn=inf,w=inf;

			for(int i=h[s];i;i=e[i].ne)

				if(dis[e[i].to][u]<mn||(dis[e[i].to][u]==mn&&e[i].to<w))

					mn=dis[e[i].to][u],w=e[i].to;

			b[s][u]=w;

		}

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

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

			a[s][i]=dis[s][i]<=2?i:b[b[s][i]][i];

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

	// {

		// for(int j=1;j<=n;j++)

			// cerr<<a[i][j]<<" ";

		// cerr<<endl;

	// }

	memset(f,-1,sizeof(f));

	printf("%.3f\n",dfs(st,ed));

	return 0;

}

巴特西

bzoj 1415: [Noi2005]聪聪和可可【期望dp+bfs】

最新文章

热门文章