背景
李煜东， (Nescafé) (19) 杯 (NOIP) 模拟赛 (T1) ， (Luogu) (P4316/TYVJ1933)
题意
给定一张 (n) 个点 (m) 条边的有边权的 (DAG) （有向无环图），起点为 (1) ，终点为 (n) 。从起点出发，每个点连接的所有点等概率地前往，求到达终点期望的总路径长度。答案保留 (2) 位小数。
解法
显然最终的状态只有一个，就是到达了 (n) 点。因此考虑逆推。
不妨考虑设 (f_x) 表示 (x) 点到终点路径的期望长度， (dis_{x,y}) 表示 (x) 点到 (y) 点的边长（要求 (x,y) 是同一条边的两端）。
根据期望的定义和性质，则转移有： (f_x=frac{ sum { f_y+dis_{x,y} } }{k}) （要求 (x,y) 是同一条边的两端， (k) 是所有符合条件的 (y) 点数量）。
易发现所有符合条件的 (y) 点数量就是 (x) 点的出度。预处理每个点 (x) 的出度 (deg_x) ，则 (f_x=frac{ sum { f_y+dis_{x,y} } }{deg_x}) （要求 (x,y) 是同一条边的两端）。拓扑排序时更新 (f) 即可。
(trick)
期望 (dp) 的设计：
(1.) 状态与一般 (dp) 无异，求什么设什么。
(2.) 转移方法有两种（都是递推）：顺推和逆推。以已知状态多的或者总状态少的一端开始推。
(3.) 转移的实现方式有填表法（从上一个状态转移而来）和刷表法（从下一个状态转移而来）两种。
设状态的例子：求 (n) 个人做某事的期望次数。显然要设 (f_i) 表示第 (i) 个人做完后的期望次数。
刷表法的例子：设 (f_i) 表示还要走 (i) 步到达终点的期望次数。转移模型为 (f_i= sum_limits{i ightarrow j} p_{i ightarrow j} imes f_j+w_{i ightarrow j}) ，其中 (p) 表示转移过程的概率， (w) 表示转移过程的权值或者对答案的贡献。
细节
(1.) 为了逆推需要建反图（对所有边取反）。
(2.) 具体更新时由于边是反向的，转移方程里的 (x,y) 要交换位置。
(3.) 拓扑排序的细节不要错。只把入度为 (0) 的点推进队列。
代码
$View$ $Code$
//省略头文件 using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,m,u,v,w; int num,head[200005],ind[100005],deg[100005]; double f[100005]; bool vis[100005]; queue q; struct edge { int ver,nxt,w; }e[200005]; inline void adde(int u,int v,int w) { e[++num].ver=v; e[num].nxt=head[u]; e[num].w=w; head[u]=num; } inline void topsort() { q.push(n); while(!q.empty()) { int x=q.front(); q.pop(); for(register int i=head[x];i;i=e[i].nxt) { int y=e[i].ver; ind[y]--; if(!ind[y]) q.push(y); f[y]+=(f[x]+e[i].w)/deg[y]; } } } int main() { n=read(); m=read(); for(register int i=1;i<=m;i++) { u=read(); v=read(); w=read(); adde(v,u,w); ind[u]++; deg[u]++; } topsort(); printf("%0.2lf ",f[1]); return 0; }