bzoj3470 Freda’s Walk

bzoj3470 Freda’s Walk

​​ Description 雨后的Poetic Island空气格外清新，于是Freda和Rainbow出来散步。 Poetic Island的交通可以看作一张n个点、m 边的有向无环图。由于刚下过雨，每条边都有一个积水深度，而恰好Freda 和Rainbow都喜欢踩水玩儿，于是Ta们从某个点出发，选择走向哪条边的概率与该边的积水深度是成正比的。即：如果Freda和Rainbow现在在点u，点u 出发的所有边的积水深度之和为s，从u到v的边积水深度为w，那么Ta们选择走向v的概率就是 w/s。 Ta们会一直走下去，直到到达一个没有出边的点，那么散步的路程长度就是走过的边的数量。更特殊的是，Freda和Rainbow在出发之前还可以选择一条边，在散步过程中无视这条边的存在（当然也可以不选择）。请你帮忙计算一下，Ta 们从0号点出发，散步的路程长度的期望值最大是多少？

Input 第一行两个正整数 n、m。 接下来m行每行三个整数u、v、w，表示从u到v有一条无向边，积水深度为w。

Output

输出Freda和Rainbow散步的路程长度的最大期望值，四舍五入保留六位小数。 Sample Input 4 5

0 1 2

0 2 1

0 3 3

1 3 1

2 3 4 Sample Output 2.000000 HINT

对于 100% 的数据，2<=n<=10000，1<=m<=100000，0<=u,v<1<=w<=1000。

Source Adera 2 杯省选模拟赛

假如没有删边的操作我的期望其实是个定值 那么我就需要去算一下删边之后带来期望的改变值了

我提前给我的序号都+1处理了因为题目中给的图是一个DAG 那么可以拓扑一下 首先从后往前拓扑 算出我当前这个节点到终点停止的期望 然后再正着拓扑一下 算出1号节点到达每个点的概率是多少 其实我只需要算1号节点的值就okay了 本想宽搜就好 但是这其实是一个dp如果直接宽搜可能存在后效性所以为了省事 其他初值直接给0 然后拓扑序dp一下 最后dp[1]就是我的答案的一种可能 接下来就是枚举我有哪些情况使得我的答案可能发生改变 那么 o(m)枚举每条边 这个针对答案的改变怎么算 首先针对我当前这个x节点 肯定是少了dp[y]w/sum[x]的期望 同时 由于少了这条边其他的概率也增大了 剩余的期望 每个期望变大的值sum[x]/(sum[x]-w) 求一下我新的期望的差值 最后对答案的贡献就是到这个点的概率*期望的该变量

#include#include#include#include#define N 11000#define M 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();return x;}struct node{ int y,z,next;}data[M];int num=0,h[N],in[N],x[M],y[M],w[M],n,m,sum[N];double dp[N],dp1[N];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;}int main(){ freopen("bzoj3470.in","r",stdin); n=read();m=read(); for (int i=1;i<=m;++i){ x[i]=read()+1,y[i]=read()+1,w[i]=read(); insert1(y[i],x[i],w[i]);++in[x[i]];sum[x[i]]+=w[i]; }queueq; for (int i=1;i<=n;++i) if (!in[i]) q.push(i); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next) { int y=data[i].y,z=data[i].z; dp[y]+=(dp[x]+1)*z/sum[y];if(--in[y]==0) q.push(y); } }memset(h,0,sizeof(h));dp1[1]=1;num=0; for (int i=1;i<=m;++i) insert1(x[i],y[i],w[i]),++in[y[i]]; for (int i=1;i<=n;++i) if (!in[i]) q.push(i); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; dp1[y]+=dp1[x]*z/sum[x];if (--in[y]==0) q.push(y); } }double ans=dp[1]; for (int i=1;i<=m;++i){ double tmp=(dp[x[i]]-(dp[y[i]]+1)*w[i]/sum[x[i]])*sum[x[i]]/(sum[x[i]]-w[i])-dp[x[i]]; ans=max(ans,dp[1]+tmp*dp1[x[i]]); }printf("%.6f",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。