题意
给定一张 $n$ 个点 $m$ 条边的无向图.
每条边有两个信息 $x, y$ , 这条边的边权是 $ax + (1 - a)y$ .
给定源点 $S$ 和汇点 $T$ , 求当 $a \in [0, 1]$ 时, $E(minpath(S, T))$ .
$n \le 200, m \le 400$ .
分析1 蒙特卡洛算法 + SPFA
不论是期望还是概率, 都是在某种量化意义下, 将试验次数取无穷大.
我们均匀取点, 进行 SPFA , 然后取平均值.
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cctype>
5 #include <cmath>
6 #include <ctime>
7 #include <vector>
8 using namespace std;
9 #define F(i, a, b) for (register int i = (a); i <= (b); i++)
10 #define fore(it, x) for (register vector<Edge>::iterator it = g[x].begin(); it != g[x].end(); it++)
11 #define db double
12 inline int rd(void) {
13 int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
14 int x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-'0'; return x*f;
15 }
16
17 const db EPS = 1e-7;
18 inline int sign(db x) { return fabs(x) < EPS ? 0 : x < 0 ? -1 : 1; }
19 inline int cmp(db x, db y) { return sign(x - y); }
20
21 const int N = 205;
22 const db INF = 1e20;
23
24 int n, m, S, T;
25 struct Edge {
26 int v; db x, y;
27 inline db d(db a) { return a * x + (1 - a) * y; }
28 };
29 vector<Edge> g[N];
30
31 inline void Init(int s, int t, db x, db y) {
32 g[s].push_back((Edge){t, x, y});
33 g[t].push_back((Edge){s, x, y});
34 }
35
36 int nT; db res;
37 int q[N], qh, qt; bool inq[N]; db dis[N];
38
39 db SPFA(db a) {
40 memset(q, 0, sizeof q), qh = qt = 0, memset(inq, false, sizeof inq), fill(dis + 1, dis + n + 1, INF);
41 q[++qt] = S, inq[S] = true, dis[S] = 0;
42 while (qh != qt) {
43 int x = q[qh = qh % n + 1];
44 fore(it, x)
45 if (cmp(dis[x] + it->d(a), dis[it->v]) < 0) {
46 dis[it->v] = dis[x] + it->d(a);
47 if (!inq[it->v])
48 q[qt = qt % n + 1] = it->v, inq[it->v] = true;
49 }
50 inq[x] = false;
51 }
52 return dis[T];
53 }
54
55 int main(void) {
56 #ifndef ONLINE_JUDGE
57 // freopen("C.in", "r", stdin);
58 #endif
59
60 srand(time(0));
61
62 n = rd(), m = rd(), S = rd(), T = rd();
63 F(i, 1, m) {
64 int s = rd(), t = rd();
65 db x, y; scanf("%lf %lf", &x, &y);
66 Init(s, t, x, y);
67 }
68
69 nT = 100000000 / (5 * n);
70 db V = 1.0 / (nT-1), a = 0; // seperated equally
71 for (int t = 1; t <= nT; t++) {
72 res += (1.0 / nT) * SPFA(a);
73 a += V;
74 }
75 printf("%0.10lf\n", res);
76
77 return 0;
78 }
分析2 Simpson积分 + SPFA
这道题要求连续性随机变量的数学期望.
设当 $a = x$ 时, 最短路的长度是 $f_a$ .
那么我们要求 $$\frac{\int_0 ^ 1 f_ada}{1 - 0}$$ .
Simpson积分套最短路.
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cctype>
5 #include <cmath>
6 #include <vector>
7 #include <map>
8 using namespace std;
9 #define F(i, a, b) for (register int i = (a); i <= (b); i++)
10 #define fore(it, x) for (register vector<Edge>::iterator it = g[x].begin(); it != g[x].end(); it++)
11 #define db double
12 inline int rd(void) {
13 int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
14 int x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-'0'; return x*f;
15 }
16
17 const int N = 205;
18 const db INF = 1e20;
19
20 int n, m, S, T;
21 struct Edge {
22 int v; db x, y;
23 inline db d(db a) { return a * x + (1 - a) * y; }
24 };
25 vector<Edge> g[N];
26
27 inline void Init(int s, int t, db x, db y) {
28 g[s].push_back((Edge){t, x, y});
29 g[t].push_back((Edge){s, x, y});
30 }
31
32 int q[N], qh, qt; bool inq[N]; db dis[N];
33 map<db, db> val;
34
35 db SPFA(db a) {
36 if (val.count(a)) return val[a];
37 memset(q, 0, sizeof q), qh = qt = 0, memset(inq, false, sizeof inq), fill(dis + 1, dis + n + 1, INF);
38 q[++qt] = S, inq[S] = true, dis[S] = 0;
39 while (qh != qt) {
40 int x = q[qh = qh % n + 1];
41 fore(it, x)
42 if (dis[x] + it->d(a) < dis[it->v]) {
43 dis[it->v] = dis[x] + it->d(a);
44 if (!inq[it->v])
45 q[qt = qt % n + 1] = it->v, inq[it->v] = true;
46 }
47 inq[x] = false;
48 }
49 return val[a] = dis[T];
50 }
51
52 inline db G(db L, db R) { return (R - L) * (SPFA(L) + SPFA(R) + 4 * SPFA((L+R)/2)) / 6; }
53 db Simpson(db L, db R) {
54 db M = (L+R)/2, RA = G(L, R), RL = G(L, M), RR = G(M, R);
55 return fabs(RA - RL - RR) < 1e-6 ? RL + RR : Simpson(L, M) + Simpson(M, R);
56 }
57
58 int main(void) {
59 #ifndef ONLINE_JUDGE
60 freopen("C.in", "r", stdin);
61 #endif
62
63 n = rd(), m = rd(), S = rd(), T = rd();
64 F(i, 1, m) {
65 int s = rd(), t = rd();
66 db x, y; scanf("%lf %lf", &x, &y);
67 Init(s, t, x, y);
68 }
69 printf("%0.10lf\n", Simpson(0, 1));
70
71 return 0;
72 }