【HNOI2011】XOR和路径 – 徐亦轲的博客

~~会了高斯消元这就是个水题~~

首先既然是XOR，那么肯定要把边权拆成二进制然后算

那么计算点1每一位到点n的期望大小

因为每一条边都是0或者1，那么规定f[i]为当前位i点到n点的XOR和期望大小（也可理解为到n点XOR和为1的概率），d[i]为i点的度数

显而易见，对于i的每一个邻点j，若边(i,j)为0，则f[i]+f[j]/d[i]，否则f[i]+(1-f[j])/d[i]。

则可以建立n元一次方程，每次解出f[1]即可。

// <xor.cpp> - 03/20/16 07:50:43
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=102;
int n;
double a[MAXN][MAXN];
vector <pair<int,int> >b[MAXN];
void gauss(){
	for(int i=1;i<=n;i++){
		for(int k=i+1;k<=n;k++)if(abs(a[k][i])>abs(a[i][i]))swap(a[k],a[i]);
		for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i];
		for(int k=i+1;k<=n;k++)
			for(int j=n+1;j>=i;j--)a[k][j]-=a[k][i]*a[i][j];
	}
	for(int i=n;i;i--)
		for(int k=i-1;k;k--)a[k][n+1]-=a[k][i]*a[i][n+1];
}
int main(){
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	n=getint();
	int m=getint();
	for(int i=0;i<m;i++){
		int u=getint(),v=getint(),w=getint();
		b[u].push_back(make_pair(v,w));
		if(u!=v)b[v].push_back(make_pair(u,w));
	}
	double ANS=0.0;
	for(int k=0;k<31;k++){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n+1;j++)a[i][j]=0.0;
		for(int i=1;i<n;i++){
			a[i][i]=1;
			for(int j=0;j<b[i].size();j++){
				if(b[i][j].second&1){
					a[i][b[i][j].first]+=1.0/b[i].size();
					a[i][n+1]+=1.0/b[i].size();
				}else a[i][b[i][j].first]+=-1.0/b[i].size();
				b[i][j].second>>=1;
			}
		}
		a[n][n]=1;
		gauss();
		ANS+=a[1][n+1]*(1<<k);
	}
	printf("%.3lf",ANS);
	return 0;
}

// <xor.cpp> - 03/20/16 07:50:43

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=102;

int n;

double a[MAXN][MAXN];

vector <pair<int,int> >b[MAXN];

void gauss(){

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

for(int k=i+1;k<=n;k++)if(abs(a[k][i])>abs(a[i][i]))swap(a[k],a[i]);

for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i];

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

for(int j=n+1;j>=i;j--)a[k][j]-=a[k][i]*a[i][j];

}

for(int i=n;i;i--)

for(int k=i-1;k;k--)a[k][n+1]-=a[k][i]*a[i][n+1];

}

int main(){

freopen("xor.in","r",stdin);

freopen("xor.out","w",stdout);

n=getint();

int m=getint();

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

int u=getint(),v=getint(),w=getint();

b[u].push_back(make_pair(v,w));

if(u!=v)b[v].push_back(make_pair(u,w));

}

double ANS=0.0;

for(int k=0;k<31;k++){

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

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

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

a[i][i]=1;

for(int j=0;j<b[i].size();j++){

if(b[i][j].second&1){

a[i][b[i][j].first]+=1.0/b[i].size();

a[i][n+1]+=1.0/b[i].size();

}else a[i][b[i][j].first]+=-1.0/b[i].size();

b[i][j].second>>=1;

}

a[n][n]=1;

gauss();

ANS+=a[1][n+1]*(1<<k);

}

printf("%.3lf",ANS);

return 0;

}

说点什么