2337: [HNOI2011]XOR和路径
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 682 Solved: 384
[Submit][Status][Discuss]
Description
几乎是一路看题解过来了。。
拖了一个星期的题目- -
已然不会概率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 ;
}