洛谷 P3211 [HNOI2011] XOR和路径

洛谷 P3211思路题目是在一个地图上的期望且可以来回走就用高斯消元因为有异或且想要用高斯消元就必须是加法所以就考虑拆位还是设表示的路径这一位为的概率那么就是的路径这一位为的概率表示的出度再推式子的时候就可以先不用考虑来回走的问题高消会给出答案就可以高斯消元,最后注意这题虽然是无向图,但是自环也不能加两次,需要特判代码#includebits/stdc.h using namespace std; struct edge{ int v,w; };int n; double a[110][110]; double abss(double x){ if(x0)return -x; else return x; } vectoredgev[110];int d[110]; const double eps1e-9; void gass(){ for(int i1;in;i){ int hi; for(int ji1;jn;j){ if(abss(a[h][i])abss(a[j][i])){ hj; } } if(i!h)swap(a[i],a[h]); double diva[i][i]; for(int ji;jn1;j)a[i][j]/div; for(int ji1;jn;j){ diva[j][i]; for(int ki;k(n1);k){ a[j][k]-a[i][k]*div; } } } for(int in-1;i1;i--){ for(int ji1;jn1;j){ a[i][n1]-(a[i][j]*a[j][n1]); } } } int main(){ // ios::sync_with_stdio(0); // cin.tie(0);cout.tie(0); int m;cinnm; for(int i1;im;i){ int x,y,z;cinxyz; if(x!y){ d[x];d[y]; v[x].emplace_back((edge){y,z}); v[y].emplace_back((edge){x,z}); }else{ d[x]; v[x].emplace_back((edge){y,z}); } } double ans0; for(int k0;k30;k){ memset(a,0,sizeof(a)); for(int i1;in;i){ a[i][i]d[i]; for(edge t:v[i]){ if(t.w(1k)){ a[i][t.v]1; a[i][n1]1; }else{ a[i][t.v]-1; } } } a[n][n]1; gass();ans(1k)*1.0*a[1][n1]; } printf(%.3lf,ans); return 0; }