# [HNOI 2011]XOR和路径

## Sample Input

2 2
1 1 2
1 2 3

## Sample Output

2.333

## 题解

$$f_u = \sum_{(u,v) \in E,\ w(u,v) = 0} \frac{f_v}{degree_u} + \sum_{(u,v) \in E,\ w(u,v) = 1} \frac{1-f_v}{degree_u}$$

 1 //It is made by Awson on 2017.10.21
2 #include <set>
3 #include <map>
4 #include <cmath>
5 #include <ctime>
6 #include <stack>
7 #include <queue>
8 #include <vector>
9 #include <string>
10 #include <cstdio>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Min(a, b) ((a) < (b) ? (a) : (b))
17 #define Max(a, b) ((a) > (b) ? (a) : (b))
18 #define Abs(x) ((x) < 0 ? (-(x)) : (x))
19 using namespace std;
20 const int N = 100;
21 const int M = 10000;
22 int st[32];
23
24 int n, m, u, v, w;
25 struct tt {
26     int to, cost, next;
27 }edge[(M<<1)+5];
28 int path[N+5], top, degree[N+5];
29 double A[N+5][N+5], ans;
30
31 double Gauss() {
32     for (int line = 1; line <= n; line++) {
33         int max_line = line;
34         for (int i = line+1; i <= n; i++) if (fabs(A[i][line]) > fabs(A[max_line][line])) max_line = i;
35         if (max_line != line) swap(A[line], A[max_line]);
36         for (int i = line+1; i <= n; i++) {
37             double div = A[i][line]/A[line][line];
38             for (int j = line; j <= n+1; j++) A[i][j] -= A[line][j]*div;
39         }
40     }
41     for (int i = n; i >= 1; i--) {
42         for (int j = i+1; j <= n; j++)
43             A[i][n+1] -= A[i][j]*A[j][n+1];
44         A[i][n+1] /= A[i][i];
45     }
46     return A[1][n+1];
47 }
48 void add(int u, int v, int w) {
49     edge[++top].to = v;
50     edge[top].cost = w;
51     edge[top].next = path[u];
52     path[u] = top; degree[v]++;
53 }
54 void work() {
55     st[0] = 1; for (int i = 1; i <= 30; i++) st[i] = st[i-1]<<1;
56     scanf("%d%d", &n, &m);
57     for (int i = 1; i <= m; i++) {
58         scanf("%d%d%d", &u, &v, &w);
60     }
61     for (int i = 0; i <= 30; i++) {
62         memset(A, 0, sizeof(A));
63         for (int u = 1; u < n; u++) {
64             A[u][u] = degree[u];
65             for (int j = path[u]; j; j = edge[j].next) {
66                 if (st[i]&edge[j].cost) A[u][edge[j].to] += 1., A[u][n+1] += 1.;
67                 else A[u][edge[j].to] -= 1.;
68             }
69         }
70         A[n][n] = 1;
71         ans += Gauss()*(double)st[i];
72     }
73     printf("%.3lf\n", ans);
74 }
75 int main() {
76     work();
77     return 0;
78 }

[HNOI 2011]XOR和路径

(0)
(0)

0条