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

2337: [HNOI2011]XOR和路径
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1170 Solved: 683
Description

Input

Output

Sample Input

Sample Output

HINT

Source

Day2

【分析】

　　这题终于自己打出来了高斯消元。没有对比代码了。。。

　　很心酸啊。。调试的时候是完全没有方向的，高斯消元还要自己一步步列式子然后消元解。。【为什么错都不知道有时候

　　这题显然是不能直接记录异或和然后DP的。

　　显然是要拆位的。

　　拆位之后f[i][0]表示从i走，走到终点，这一位异或和为0的概率。

　　f[i][0]=f[j][0]*p (i->j 这一位边权为0)+f[j][1]*p (i->j 这一位边权为1)

　　反之不写了

　　f[n][0]=1 f[n][1]=0

　　就是(2*n)^2规模的高斯消元。

　　然后用f[1][1]乘这一位的贡献加进答案里面就好。

　　一开始被卡精，eps太小，后来数组爆一位！！醉了！！

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 #define Maxn 110
 9 #define Maxm 10010
10 const double eps=1e-60;
11 
12 struct node
13 {
14     int x,y,c,next;
15 }t[Maxm*2];
16 int first[Maxn],len;
17 double d[Maxn];
18 void ins(int x,int y,int c)
19 {
20     d[x]+=1.0;
21     t[++len].x=x;t[len].y=y;t[len].c=c;
22     t[len].next=first[x];first[x]=len;
23 }
24 
25 bool dcmp(double x) {return fabs(x)>eps;}
26 
27 double a[2*Maxn][2*Maxn],f[2*Maxn];
28 void gauss(int n)
29 {
30     for(int i=1;i<n;i++)
31     {
32         // if(a[i][i]==0) continue;
33         int t=i;
34         for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[t][i])) t=j;
35         if(t!=i)
36         {
37             for(int j=1;j<=n;j++) swap(a[i][j],a[t][j]);
38         }
39         for(int j=i+1;j<=n;j++)
40         {
41             double t=a[j][i]/a[i][i];
42             if(dcmp(a[j][i]))
43             {
44                 for(int k=1;k<=n;k++) a[j][k]-=a[i][k]*t;
45             }
46         }
47     }
48     for(int i=n-1;i>=1;i--)
49     {
50         for(int j=i+1;j<n;j++) a[i][n]+=f[j]*a[i][j];
51         f[i]=-a[i][n]/a[i][i];
52     }
53 }
54 
55 int main()
56 {
57     int n,m,mx=0;
58     scanf("%d%d",&n,&m);
59     len=0;memset(first,0,sizeof(first));
60     for(int i=1;i<=n;i++) d[i]=0;
61     for(int i=1;i<=m;i++)
62     {
63         int x,y,c;
64         scanf("%d%d%d",&x,&y,&c);
65         mx=max(mx,c);
66         ins(x,y,c);
67         if(x!=y) ins(y,x,c);
68     }
69     int l=0;while((1<<l)<=mx) l++;
70     double ans=0;
71     for(int i=0;i<=l;i++)
72     {
73         for(int j=0;j<=n+n;j++) for(int k=0;k<=n+n;k++) a[j][k]=0;
74         for(int j=1;j<n;j++)
75         {
76             a[j][j]=1.0;a[j+n][j+n]=1.0;
77             for(int k=first[j];k;k=t[k].next)
78             {
79                 int y=t[k].y;
80                 if(t[k].c&(1<<i)) a[j][y+n]-=1.0/d[j],a[j+n][y]-=1.0/d[j];
81                 else a[j][y]-=1.0/d[j],a[j+n][y+n]-=1.0/d[j];
82             }
83             a[j][(n<<1)+1]=a[j+n][(n<<1)+1]=0;
84         }
85         a[n][n]=1.0;a[n+n][n+n]=1.0;
86         a[n][(n<<1)+1]=-1.0;a[n<<1][(n<<1)+1]=0;
87         gauss((n<<1)+1);
88         // printf("%.10lf
",f[n+1]);
89         ans+=1.0*(1<<i)*f[n+1];
90     }
91     printf("%.3lf
",ans);
92     return 0;
93 }

View Code

【怎么说回家前A掉这题还是很兴奋的

【也说明我能自己打出概率的高斯消元了耶！

2017-04-22 16:06:09