记录编号	393732	评测结果	AAAAAAAAAA
题目名称	[HNOI 2011] XOR和路径	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.464 s
提交时间	2017-04-12 00:07:44	内存使用	0.63 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 102
typedef double real;
const real eps = 1e-8;
typedef real matrix[MAXN][MAXN];
matrix A;
real x[MAXN];
void gauss_jordan(int n){
  for(int i = 0; i < n; i++){
    int r = i;
    for(int j = i+1; j < n; j++)if(fabs(A[j][i]) > fabs(A[r][i]))r = j;
    if(fabs(A[r][i]) < eps)continue;
    if(r != i)for(int j = 0; j <= n; j++)swap(A[i][j], A[r][j]);
    for(int k = 0; k < n; k++)if(k != i)
      for(int j = n; j >= i; j--)A[k][j] -= A[k][i]/A[i][i]*A[i][j];
  }
  for(int i = 0; i < n; i++)x[i] = A[i][n]/A[i][i];
}
int deg[MAXN];
struct edge{
  int to, val, next;
}es[MAXN*MAXN*2]; int head[MAXN], _etot;
inline void addedge(int u, int v, int c){
  es[++_etot] = (edge){v, c, head[u]}; head[u] = _etot;
  deg[u]++;
}
int main(){
  freopen("xorpath.in", "r", stdin);
  freopen("xorpath.out", "w", stdout);
  int n, m;
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; i++){
    int u, v, c;
    scanf("%d %d %d", &u, &v, &c);    
    u--, v--;
    addedge(u, v, c); if(u != v)addedge(v, u, c);
  }
  real ans = 0;
  for(int h = 0; h <= 30; h++){
    memset(A, 0, sizeof A); memset(x, 0, sizeof x);
    for(int u = 0; u < n-1; u++){
      for(int i = head[u]; i; i = es[i].next){
        if(es[i].val & (1<<h))A[u][es[i].to] += 1, A[u][n] += 1;
        else A[u][es[i].to] -= 1;
      }
      A[u][u] += deg[u];
    }
    gauss_jordan(n);
    ans += x[0]*(1<<h);
  }
  printf("%.3lf\n", ans);
  return 0;
}