3388. 【NOIP2013模拟】绿豆蛙的归宿 (Standard IO)
Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits
做法:仔细观察可以发现,这题跟所谓的期望其实没多大关系。。用暴力算答案的复杂度为O(M), 所以搜索即可。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 100007 5 using namespace std; 6 struct edge 7 { 8 int to, next; 9 double w; 10 }e[2 * N]; 11 int n, m, ls[N], tot, cd[N], rd[N]; 12 double dis[N]; 13 14 void add(int x, int y, double z) 15 { 16 e[++tot].to = y; 17 e[tot].w = z; 18 e[tot].next = ls[x]; 19 ls[x] = tot; 20 } 21 22 void dfs(int x, double s, double tot) 23 { 24 if (x == n) 25 { 26 dis[n] += tot * s; 27 return; 28 } 29 s *= (1.0 / (double)cd[x]); 30 for (int i = ls[x]; i; i = e[i].next) 31 { 32 tot += e[i].w; 33 dfs(e[i].to, s, tot); 34 tot -= e[i].w; 35 } 36 } 37 38 int main() 39 { 40 scanf("%d%d", &n, &m); 41 int x, y; 42 double z; 43 for (int i = 1; i <= m; i++) 44 { 45 scanf("%d%d", &x, &y); 46 scanf("%lf", &z); 47 cd[x]++; 48 add(x, y, z); 49 } 50 dfs(1, 1.0, 0); 51 printf("%.2f", dis[n]); 52 }