$f[x]=\frac{\sum f[y]~xor~val[p]}{deg[x]}$
转化为:
$f[x]*deg[x]=\sum f[y]~xor~val[p]$
由于本题有重边或者自环,具有后效性,因此不能直接求解。
每一位进行高斯消元:
$f[x]*deg[x]=\sum\limits_{val[p]=1}(1-f[y])+\sum\limits_{val[p]=0}f[y]$
变量放左边,常量放右边
$f[x]*deg[x]+\sum\limits_{val[p]=1}f[y]-\sum\limits_{val[p]=0}f[y]=\sum\limits_{val[p]=1}1$
高斯消元乱搞即可。
注意$f[n]=0$
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
#define eps 1e-6
using namespace std;
const int M=1e4+10,N=105;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct edge{int y,w,next;}a[M<<1];int len,last[N],deg[N];
inline void ins(int x,int y,int w){a[++len]=(edge){y,w,last[x]};last[x]=len;}
double d[N][N],ans;int n,m,mx;
inline void gauss()
{
for(int i=1;i<n;i++)
{
int x=i;
for(int j=i+1;j<n;j++)if(fabs(d[j][i])>fabs(d[x][i]))x=j;
//if(fabs(d[x][i])<eps)continue;
for(int j=1;j<=n+1;j++)swap(d[x][j],d[i][j]);
for(int k=1;k<n;k++)
if(k!=i)
{
double tmp=d[k][i]/d[i][i];
for(int j=n+1;j>=i;j--)
d[k][j]-=tmp*d[i][j];
}
}
}
int main()
{
qr(n),qr(m);ans=0;mx=0;
for(int i=1,x,y,w;i<=m;i++){qr(x),qr(y),qr(w),ins(x,y,w),++deg[x],mx=max(mx,w);if(x^y)ins(y,x,w),++deg[y];}
for(int p=1;p<=mx;p<<=1)
{
d[n][n]=1;//d[n][n+1]=0;
for(int x=1;x<n;x++)
{
d[x][x]=deg[x];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k].w&p)++d[x][n+1],++d[x][y];
else --d[x][y];
}
}
gauss();
ans+=d[1][n+1]/d[1][1]*p;
memset(d,0,sizeof(d));
}
printf("%.3lf\n",ans);
return 0;
}
最后一次更新于2019-11-14
0 条评论