8
21
2016
0

[BZOJ3036] 绿豆蛙的归宿

考虑dp

设$d[x]$为到达$x$号点时的期望长度

因为会随机选一个点,所以到达$x$号点的期望长度为所有能到x号点的点的期望长度乘以到达x号点的边长度

这就告诉我们需要拓扑排序

首先边反向(这样不用处理根本到不了终点的点,而且可以避免计算错误)

(当然反向是比正向快多了)(我正向TLE了)

然后直接在拓扑序上面搞就行

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,h[N],en,nxt[N];
double d[N],p[N];
queue<int> Q;

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Edge{int b,v,next;}e[N<<1];
inline void AddEdge(const int &sa,const int &sb,const int &sc){e[++en].b=sb;nxt[sb]++;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}

inline void bfs(){
for(register int i=1;i<=n;i++)p[i]=1.0/nxt[i];
Q.push(n);
while(!Q.empty()){
	int u=Q.front();Q.pop();
	for(register int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		d[v]+=p[v]*(d[u]+e[i].v);
		if(!--nxt[v])Q.push(v);
	}
}
}

int main(){
freopen("3036.in","r",stdin);
freopen("3036.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=m;i++){
	int u,v,w;
    Read(u);Read(v);Read(w);
    AddEdge(v,u,w);
}
bfs();
printf("%.2lf\n",d[1]);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 797

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com