期望题目
设f[x] 表示从x出发 所经过的 路径 期望长度
若从x出发有k条边 所以f[y]=1/k∑(f[x]+zi);
显然 f[n]=0;
C++ 代码
//f[x]表示从x节点走到终点期望路经长度
//f[n]==0
//终点是一切概率的结束 也是一切期望的开始;
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x) {
x=0;
T f=1,ch=getchar();
while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
x*=f;
}
const int N=200100;
int n,m,x,y,v,tot,deg[N],out[N],lin[N];
double f[N];
struct gg {
int y,next,v;
}a[N<<1];
inline void add(int x,int y,int v) {
a[++tot].y=y;
a[tot].next=lin[x];
lin[x]=tot;
a[tot].v=v;
}
queue<int>q;
int main() {
read(n); read(m);
for(int i=1;i<=m;i++) {
read(x); read(y); read(v);
deg[x]++,out[x]++;
add(y,x,v);
}
q.push(n);
while(q.size()) {
int x=q.front();q.pop();
for(int i=lin[x];i;i=a[i].next) {
int y=a[i].y;
f[y]+=(f[x]+a[i].v)/deg[y];
out[y]--;
if(!out[y]) q.push(y);
}
}
printf("%.2lf\n",f[1]);
}
f[n]=0吧?
能给蒟蒻解释一下期望的那个递推式子$f[y]=\frac{1}{k} \sum (f[y]+zi)$吗?
对不起啊 公式写错了 代码里的是正确的 f[y]=1/k∑(f[x]+zi) 我们这里考虑从x走向y 因为期望是等于sigma概率*贡献的 这是期望的定义 然后我们发现对于这个题目 每一条边的被选到的概率是一样的 假设一共有k条边 所以 每个的概率是 1/k 然后我们考虑 贡献是什么 每个边的贡献 就是自己的这条边的边权+到达这条边之前的值f[x] 求出f[y] 不懂得话可以再问
ok,了解了