正题

题目链接:https://www.luogu.com.cn/problem/P3211

题目大意

一个\(n\)个点\(m\)条边的无向图，从\(1\)到\(n\)随机游走。求期望路径异或和。

\(2\leq n\leq 100,1\leq m\leq 10^4\)

解题思路

因为是异或的期望，很难直接处理，所以考虑按位考虑每一位是\(1\)的概率。

然后\(n\)很小就是一个很显然的高斯消元了。设\(f_i\)表示\(i\sim n\)是\(1\)的概率。

\[f_x=\frac{1}{deg_x}(\sum_{x->y,w=1}(1-f_y)+\sum_{x->y,w=0}f_y)
\]

时间复杂度\(O(n^3\log w_i)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=110;

struct node{

	int to,next,w;

}a[N*N*2];

int n,m,tot,deg[N],ls[N];

double f[N],ans;

void addl(int x,int y,int w){

	a[++tot].to=y;

	a[tot].next=ls[x];

	ls[x]=tot;a[tot].w=w;

	return;

}

namespace G{

	double a[N][N],b[N];

	void init(){

		for(int i=1;i<=n;i++){

			for(int j=1;j<=n;j++)a[i][j]=0;

			b[i]=0;

		}

		return;

	}

	void solve(double *f){

		for(int i=1;i<=n;i++){

			int z=i;

			for(int j=i+1;j<=n;j++)

				if(a[j][i]>a[z][i])z=i;

			swap(a[i],a[z]);swap(b[i],b[z]);

			double inv=a[i][i];

			for(int j=i;j<=n;j++)

				a[i][j]=a[i][j]/inv;

			b[i]=b[i]/inv;

			for(int j=i+1;j<=n;j++){

				double rate=-a[j][i];

				for(int k=i;k<=n;k++)

					a[j][k]+=a[i][k]*rate;

				b[j]+=b[i]*rate;

			}

		}

		for(int i=n-1;i>=1;i--){

			for(int j=i+1;j<=n;j++)

				b[i]-=b[j]*a[i][j]/a[j][j];

			f[i]=b[i];

		}

		return;

	}

};

void solve(int w){

	G::init();G::a[n][n]=1;

	for(int x=1;x<n;x++){

		for(int i=ls[x];i;i=a[i].next){

			int y=a[i].to;

			if(a[i].w&w)G::a[x][y]++,G::b[x]++;

			else G::a[x][y]--;

		}

		G::a[x][x]+=deg[x];

	}

	G::solve(f);ans+=(double)w*f[1];

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		int x,y,w;

		scanf("%d%d%d",&x,&y,&w);

		deg[x]++;addl(x,y,w);

		if(x!=y)deg[y]++,addl(y,x,w);

	}

	for(int i=0;i<=30;i++)

		solve(1<<i);

	printf("%.3lf\n",ans);

	return 0;

}

巴特西

P3211-[HNOI2011]XOR和路径【高斯消元】

正题

题目大意

解题思路

code

最新文章

热门文章