题意:
给一个数据大小为S的数据包, 每一次发送需要K秒(单向),现在要从节点0 发送到节点 n-1。
其中有n - 1条路径, 每条路径都有一个传输成功率。
问传输成功所需最小时间的期望。
思路:
最小时间的期望, 即最大的传输成功率, 最小的传输次数, 即只传输成功一次所需要的时间的期望。
利用dijkstra or 中途相遇法进行求解从节点0到节点n-1的最大成功率。
设其为p。
我们所要求的是传输成功一次需要的次数的期望, 这满足几何分布, so, E = 1 / p。
所以,ans = E * 2 * K * S
代码:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 110
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define pa {system("pause");}
25 #define p(x) printf("%d\n", x)
26 #define pd(x) printf("%.7lf\n", x)
27 #define k(x) printf("Case %d: ", ++x)
28 #define s(x) scanf("%d", &x)
29 #define sd(x) scanf("%lf", &x)
30 #define mes(x, d) memset(x, d, sizeof(x))
31 #define do(i, x) for(i = 0; i < x; i ++)
32 #define dod(i, x, l) for(i = x; i >= l; i --)
33 #define doe(i, x) for(i = 1; i <= x; i ++)
34 int n, m, s, k;
35 int kcase = 0;
36 double f[MAXN][MAXN];
37 void solve()
38 {
39 for(int i = 0; i < n; i ++)
40 f[i][i] = 1.0;
41 for(int t = 0; t < n; t ++)
42 for(int i = 0; i < n; i ++)
43 for(int j = 0; j < n; j ++)
44 f[i][j] = max(f[i][j], f[i][t] * f[t][j]);
45 double ans = f[0][n-1];
46 double ex = (1.0 / ans) * (2.0 * k * s);
47 printf("Case %d: %.7lf\n", ++ kcase, ex);
48 }
49
50 int main()
51 {
52 int T;
53 scanf("%d", &T);
54 while(T --)
55 {
56 scanf("%d %d %d %d", &n, &m, &s, &k);
57 int u, v, p;
58 for(int i = 0; i < n; i ++)
59 for(int j = 0; j < n; j ++)
60 f[i][j] = 0.0;
61 for(int i = 0; i < m; i ++)
62 {
63 scanf("%d %d %d", &u, &v, &p);
64 f[u][v] = f[v][u] = p / 100.0;
65 }
66 solve();
67 }
68 return 0;
69 }