【概率DP/高斯消元】BZOJ 2337:[HNOI2011]XOR和路径

2337: [HNOI2011]XOR和路径

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 682  Solved: 384
[Submit][Status][Discuss]

Description

【概率DP/高斯消元】BZOJ 2337:[HNOI2011]XOR和路径


  几乎是一路看题解过来了。。
  拖了一个星期的题目- -
  已然不会概率DP(说得好像什么时候会过一样),高斯消元(打一次copy一遍)。
  发现异或题目的新解决方法:按位处理。。
  发现DP新方法:高斯消元。
  f[k][i]代表第k位权值起点为i到终点时答案的期望值。
  则对一条边<i,j>有两种转移:当边权为0,f[k][j]/deg[i].当边权为1,(1-f[k][j])/deg[i]。
  由于是一个无向图。
  topo DP很不好搞。
  只能高斯消元。
 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> using namespace std; struct edge{
int to,c,last;
}edge[]; int last[],tot=,in[],n; double f[][],V[]; inline int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();
return x;
} void add(int u,int v,int c)
{
edge[++tot].to=v,edge[tot].last=last[u],edge[tot].c=c,last[u]=tot;
in[u]++;
} void chan(int a,int b)
{
for(int i=;i<=n+;i++)
swap(f[a][i],f[b][i]);
} double gauss()
{
for(int i=;i<=n;i++)
{
if(!f[i][i])
{
for(int j=i+;j<=n;j++)
if(f[i][j])
chan(i,j);
}
for(int j=;j<=n;j++)
{
if(i==j)continue;
double xi=f[j][i]/f[i][i];
for(int k=;k<=n+;k++)f[j][k]-=xi*f[i][k];
}
}
return f[][n+]/f[][];
} int main()
{
int m,u,v,c;
n=read(),m=read();
for(int i=;i<=m;i++)
{
u=read();v=read();c=read();
add(u,v,c);
if(u!=v)add(v,u,c);
}
for(int i=;i<;i++)
{
for(int j=;j<n;j++)
{
f[j][j]=;
for(int k=last[j];k;k=edge[k].last)
{
if(edge[k].c&(<<i))f[j][edge[k].to]+=(double)1.0/in[j],f[j][n+]+=(double)1.0/in[j];
else f[j][edge[k].to]-=(double)1.0/in[j];
}
}
f[n][n]=;
V[i]=gauss();
memset(f,,sizeof(f));
}
double ans=;
int cnt=;
for(int i=;i<;i++)ans+=cnt*V[i],cnt*=;
printf("%.3lf",ans);
return ;
}
上一篇:ASP.NET Core 中 HttpContext 详解与使用 | Microsoft.AspNetCore.Http 详解


下一篇:BZOJ 2337: [HNOI2011]XOR和路径( 高斯消元 )