首页 > 代码库 > BZOJ2337 [HNOI2011]XOR和路径
BZOJ2337 [HNOI2011]XOR和路径
题意:有一个无向图,边带权,从点1开始,每次随机选择与这个点相邻的一条边走到另一个点,直到走到点n.权值为所有走过的边的异或和(若一条边经过多次则被异或多次),求权值的期望值。
思路:将每一位拆开。那么相当于边上的权值只有0,1.
由于到达n就立即停止,我们定义f[i]表示从i到达n的期望值。
那么显然f[n]=0,对于i!=n,我们列出其转移方程:
for all x near i if (Edge(x,i)==0) f[i]+=f[x]/du[i] else f[i]+=(1-f[x])/du[i].(大概是这个意思)
然后就有n-1个方程,有高斯消元求解即可。
最终的答案就是f[1]*2^i(假设当前是第i位)
将所有位的答案累加即可。
Code:
#include <cstdio> #include <cstring> #include <cctype> #include <iostream> #include <algorithm> using namespace std; typedef double f2; #define N 110 #define M 10010 int head[N], next[M << 1], end[M << 1], len[M << 1], du[N]; void addedge(int a, int b, int _len) { static int q = 1; len[q] = _len; end[q] = b; next[q] = head[a]; head[a] = q++; } f2 A[N][N]; #define _abs(x) ((x)>0?(x):-(x)) void Gauss(int n) { register int i, j, k; f2 tmp; for(i = 1; i <= n; ++i) { k = i; for(j = i + 1; j <= n; ++j) if (_abs(A[j][i]) > _abs(A[k][i])) k = j; if (k != i) for(j = i; j <= n + 1; ++j) swap(A[i][j], A[k][j]); for(j = i + 1; j <= n; ++j) { tmp = -A[j][i] / A[i][i]; A[j][i] = 0; for(k = i + 1; k <= n + 1; ++k) A[j][k] += tmp * A[i][k]; } } for(i = n; i >= 1; --i) { for(j = i + 1; j <= n; ++j) A[i][n + 1] -= A[j][n + 1] * A[i][j]; A[i][n + 1] /= A[i][i]; } } int main() { #ifndef ONLINE_JUDGE freopen("tt.in", "r", stdin); #endif int n, m; scanf("%d%d", &n, &m); register int i, j; int a, b, x; for(i = 1; i <= m; ++i) { scanf("%d%d%d", &a, &b, &x); if (a != b) { ++du[a], ++du[b]; addedge(a, b, x); addedge(b, a, x); } else { ++du[a]; addedge(a, a, x); } } f2 res = 0; for(int bit = 0; bit < 30; ++bit) { memset(A, 0, sizeof(A)); for(i = 1; i < n; ++i) { A[i][i] = 1; for(j = head[i]; j; j = next[j]) { if ((len[j] >> bit) & 1) A[i][n + 1] += 1 / (f2)du[i], A[i][end[j]] += 1 / (f2)du[i]; else A[i][end[j]] -= 1 / (f2)du[i]; } } A[n][n] = 1; Gauss(n); res += A[1][n + 1] * (1 << bit); } printf("%.3lf", res); return 0; }
BZOJ2337 [HNOI2011]XOR和路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。