NC20086. [HNOI2011]XOR和路径
描述
直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 1 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 N 号节点为止，便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。
输入描述
从文件input.txt中读入数据，输入文件的第一行是用空格隔开的两个正整数N和M，分别表示该图的节点数和边数。紧接着的M行，每行是用空格隔开的三个非负整数u，v和w(1≤u,v≤N，0≤w≤109)，表示该图的一条边(u,v)，其权值为w。输入的数据保证图连通，30%的数据满足N≤30，100%的数据满足2≤N≤100，M≤10000，但是图中可能有重边或自环。
输出描述
输出文件 output.txt 仅包含一个实数，表示上述算法得到的路径的“XOR 和”的期望值，要求保留三位小数。（建议使用精度较高的数据类型进行计算）
示例1
输入:
2 2 1 1 2 1 2 3
输出:
2.333
C++14(g++5.4) 解法, 执行用时: 19ms, 内存消耗: 700K, 提交时间: 2020-08-06 22:46:01
//Author:XuHt
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 106;
int n, m;
double a[N][N], b[N], ans;
vector<pair<int, int> > e[N];
void work() {
for (int i = 1; i < n; i++) {
int now = i;
for (int j = i + 1; j < n; j++)
if (fabs(a[j][i]) > fabs(a[now][i])) now = j;
for (int j = 0; j <= n; j++) swap(a[i][j], a[now][j]);
for (int j = i + 1; j <= n; j++) {
double rate = a[j][i] / a[i][i];
for (int k = 0; k <= n; k++) a[j][k] = a[i][k] * rate - a[j][k];
}
}
for (int i = n; i; i--) {
for (int j = i + 1; j <= n; j++) a[i][0] -= a[i][j] * b[j];
b[i] = a[i][0] / a[i][i];
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
e[x].push_back(make_pair(y, z));
if (x != y) e[y].push_back(make_pair(x, z));
}
for (int i = 0; i < 31; i++) {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for (int x = 1; x <= n; x++) a[x][x] = 1;
for (int x = 1; x < n; x++) {
int s = e[x].size();
for (int j = 0; j < s; j++) {
int y = e[x][j].first, z = e[x][j].second;
double w = 1.0 / s;
if ((z >> i) & 1) {
a[x][y] += w;
a[x][0] += w;
} else a[x][y] -= w;
}
}
work();
ans += b[1] * (1 << i);
}
printf("%.3f\n", ans);
return 0;
}
C++ 解法, 执行用时: 16ms, 内存消耗: 664K, 提交时间: 2022-02-08 11:15:43
#include<bits/stdc++.h>
using namespace std;
int n,m,hd[101],cnt,d[101],p[101]={1},u,v,w;
double a[101][101],f[101],ans;
struct ee{int to,nt,w;}e[20001];
void add(int u,int v,int w){e[++cnt].to=v;e[cnt].w=w;e[cnt].nt=hd[u];hd[u]=cnt;d[v]++;}
void gs(){
for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++){double tmp=a[j][i]/a[i][i];for(int k=1;k<n+2;k++)a[j][k]-=a[i][k]*tmp;}
for(int i=n;i;i--){f[i]=a[i][n+1]/a[i][i];for(int j=i-1;j;j--)a[j][n+1]-=a[j][i]*f[i];}
}
int main(){
cin>>n>>m;
memset(hd,-1,sizeof hd);
for(int i=1;i<31;i++)p[i]=p[i-1]*2;
for(int i=1;i<=m;i++){cin>>u>>v>>w;add(u,v,w);if(u-v)add(v,u,w);}
for(int i=0;i<31;i++){
memset(a,0,sizeof(a));
a[n][n]--;
for(int u=1;u<n;u++){
a[u][u]=-1;
for(int j=hd[u];j+1;j=e[j].nt){int v=e[j].to;if(~e[j].w&p[i])a[u][v]+=1.0/d[u];else a[u][n+1]-=1.0/d[u],a[u][v]-=1.0/d[u];}
}
gs();
ans+=f[1]*p[i];
}
printf("%.3lf",ans);
return 0;
}