洛谷$P4316$ 绿豆蛙的归宿 期望

时间:2022-08-27 02:58:53

正解:期望

解题报告:

传送门!

看懂题目还是挺水的$(bushi$

三个方法,但因为题目太水了懒得一一介绍了,,,反正都是期望,,,$so$随便港个最简单的趴$QwQ$

直接考虑每条边的贡献,就会是概率*长度

概率按拓扑序求(当然如果直接求个概率而已的话可以直接用dfs来着,,,

然后就做完辽,,,?

$maya$我做的题越来越水辽,,,/流泪

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define int long long
#define lf long double
#define t(i) edge[i].to
#define w(i) edge[i].wei
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) const int N=+;
int n,m,head[N],out[N],ed_cnt,in[N];
lf f[N],as;
bool vis[N];
struct ed{int to,nxt,wei;}edge[N<<];
queue<int>Q; il int read()
{
ri x=;rb y=;rc ch=gc;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void ad(ri x,ri y,ri z){edge[++ed_cnt]=(ed){y,head[x],z};head[x]=ed_cnt;}
il void topsort()
{
rp(i,,n)if(!in[i])Q.push(i);
while(!Q.empty())
{
int nw=Q.front();Q.pop();
e(i,nw)
{
f[t(i)]+=(lf)f[nw]/out[nw];as+=(lf)f[nw]/out[nw]*w(i);
--in[t(i)];if(!in[t(i)])Q.push(t(i));
}
}
} signed main()
{
freopen("4316.in","r",stdin);freopen("4316.out","w",stdout);
n=read();m=read();rp(i,,m){ri x=read(),y=read(),z=read();ad(x,y,z);++in[y];++out[x];}
f[]=;topsort();printf("%.2Lf\n",as);
return ;
}

这儿是代码$QAQ$