主要思路
首先,这道题是概率和期望分开算的,进行 DP 时实质上是对概率进行 DP。考虑拆位,设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率,那么显然:
\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]
其中,\((1 – dp_b[v])\)为\(v\)为\(0\)的概率,最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。
代码
// P3211.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 110;
const double eps = 1e-8;
int n, m, head[MAX_N], current, deg[MAX_N];
double matrix[MAX_N][MAX_N], ans[MAX_N];
struct edge
{
int to, nxt, weight;
} edges[20010];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void build_matrix(int pos)
{
matrix[n][n] = 1;
for (int pt = 1; pt <= n - 1; pt++)
{
matrix[pt][pt] = deg[pt];
for (int i = head[pt]; i != -1; i = edges[i].nxt)
if (edges[i].weight & pos)
matrix[pt][edges[i].to]++, matrix[pt][n + 1]++;
else
matrix[pt][edges[i].to]--;
}
}
void gauss()
{
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
if (fabs(matrix[j][i]))
{
double rate = matrix[j][i] / matrix[i][i];
for (int k = i; k <= n + 1; k++)
matrix[j][k] -= rate * matrix[i][k];
}
}
for (int i = n; i >= 1; i--)
{
for (int j = i + 1; j <= n; j++)
matrix[i][n + 1] -= matrix[i][j] * ans[j];
ans[i] = matrix[i][n + 1] / matrix[i][i];
}
memset(matrix, 0, sizeof(matrix));
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
int mx = 0;
for (int i = 1, x, y, z; i <= m; i++)
{
scanf("%d%d%d", &x, &y, &z);
addpath(x, y, z), deg[x]++, mx = max(mx, z);
if (x != y)
addpath(y, x, z), deg[y]++;
}
double answer = 0;
for (int i = 1; i <= mx; i <<= 1)
build_matrix(i), gauss(), answer += ans[1] * i;
printf("%.3lf", answer);
return 0;
} // P3211.cpp
// P3211.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 110;
const double eps = 1e-8;
int n, m, head[MAX_N], current, deg[MAX_N];
double matrix[MAX_N][MAX_N], ans[MAX_N];
struct edge
{
int to, nxt, weight;
} edges[20010];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void build_matrix(int pos)
{
matrix[n][n] = 1;
for (int pt = 1; pt <= n - 1; pt++)
{
matrix[pt][pt] = deg[pt];
for (int i = head[pt]; i != -1; i = edges[i].nxt)
if (edges[i].weight & pos)
matrix[pt][edges[i].to]++, matrix[pt][n + 1]++;
else
matrix[pt][edges[i].to]--;
}
}
void gauss()
{
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
if (fabs(matrix[j][i]))
{
double rate = matrix[j][i] / matrix[i][i];
for (int k = i; k <= n + 1; k++)
matrix[j][k] -= rate * matrix[i][k];
}
}
for (int i = n; i >= 1; i--)
{
for (int j = i + 1; j <= n; j++)
matrix[i][n + 1] -= matrix[i][j] * ans[j];
ans[i] = matrix[i][n + 1] / matrix[i][i];
}
memset(matrix, 0, sizeof(matrix));
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
int mx = 0;
for (int i = 1, x, y, z; i <= m; i++)
{
scanf("%d%d%d", &x, &y, &z);
addpath(x, y, z), deg[x]++, mx = max(mx, z);
if (x != y)
addpath(y, x, z), deg[y]++;
}
double answer = 0;
for (int i = 1; i <= mx; i <<= 1)
build_matrix(i), gauss(), answer += ans[1] * i;
printf("%.3lf", answer);
return 0;
} // P3211.cpp
// P3211.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 110; const double eps = 1e-8; int n, m, head[MAX_N], current, deg[MAX_N]; double matrix[MAX_N][MAX_N], ans[MAX_N]; struct edge { int to, nxt, weight; } edges[20010]; void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].nxt = head[src]; edges[current].weight = weight, head[src] = current++; } void build_matrix(int pos) { matrix[n][n] = 1; for (int pt = 1; pt <= n - 1; pt++) { matrix[pt][pt] = deg[pt]; for (int i = head[pt]; i != -1; i = edges[i].nxt) if (edges[i].weight & pos) matrix[pt][edges[i].to]++, matrix[pt][n + 1]++; else matrix[pt][edges[i].to]--; } } void gauss() { for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) if (fabs(matrix[j][i])) { double rate = matrix[j][i] / matrix[i][i]; for (int k = i; k <= n + 1; k++) matrix[j][k] -= rate * matrix[i][k]; } } for (int i = n; i >= 1; i--) { for (int j = i + 1; j <= n; j++) matrix[i][n + 1] -= matrix[i][j] * ans[j]; ans[i] = matrix[i][n + 1] / matrix[i][i]; } memset(matrix, 0, sizeof(matrix)); } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); int mx = 0; for (int i = 1, x, y, z; i <= m; i++) { scanf("%d%d%d", &x, &y, &z); addpath(x, y, z), deg[x]++, mx = max(mx, z); if (x != y) addpath(y, x, z), deg[y]++; } double answer = 0; for (int i = 1; i <= mx; i <<= 1) build_matrix(i), gauss(), answer += ans[1] * i; printf("%.3lf", answer); return 0; } // P3211.cpp