【BZOJ 3640】JC的小苹果 (高斯消元,概率DP)

JC的小苹果

Submit: 432  Solved: 159

Description

   让我们继续JC和DZY的故事。

    “你是我的小丫小苹果,怎么爱你都不嫌多!”

    “点亮我生命的火,火火火火火!”

    话说JC历经艰辛来到了城市B,但是由于他的疏忽DZY偷走了他的小苹果!没有小苹果怎么听歌!他发现邪恶的DZY把他的小苹果藏在了一个迷宫里。JC在经历了之前的战斗后他还剩下hp点血。开始JC在1号点,他的小苹果在N号点。DZY在一些点里放了怪兽。当JC每次遇到位置在i的怪兽时他会损失Ai点血。当JC的血小于等于0时他就会被自动弹出迷宫并且再也无法进入。

    但是JC迷路了,他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的,一共有m条,怪兽无法被杀死。现在JC想知道他找到他的小苹果的概率。

    P.S.大家都知道这个系列是提高组模拟赛,所以这是一道送分题balabala

Input

第一行三个整数表示n,m,hp。接下来一行整数,第i个表示jc到第i个点要损失的血量。保证第1个和n个数为0。接下来m行每行两个整数a,b表示ab间有一条无向边。

Output

    仅一行,表示JC找到他的小苹果的期望概率,保留八位小数。

Sample Input

3 3 2
0 1 0
1 2
1 3
2 3

Sample Output

0.87500000

HINT

对于100%的数据 2<=n<=150,hp<=10000,m<=5000,保证图联通。

Source

【分析】

  f[i][j]表示剩下i的体力,走到j点的概率。

  显然f[hp][1]=1,$Ans=sum_{i=1}^{hp} f[i][n]$

  状态转移:$f[i][j]=f[i+lose[j]][k]*dfrac{1}{d[k]}$

  但是lose[j]有可能为0,状态转移可能成环,这时候就要高斯消元。

  lose[j]不为0直接放入常数项。

  就写成了$f[i][j]=f[i][k]*dfrac{1}{d[k]}+...+b[j]$

  这样高斯消元是$O(n^{3}*hp)$会超时

  发现对于每个i,高斯消元前面部分是一样的,只是常数项变了。于是只做一次高斯消元,然后记录路径,常数项直接照路径做就好了。

  【注意如果到达n就不会再走出去了

  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 160
  9 #define Maxm 5010
 10 #define Maxl 10010
 11 const double eps=1e-8;
 12 
 13 int dcmp(double x)
 14 {
 15     return abs(x)>eps;
 16 }
 17 
 18 int ls[Maxn];
 19 double f[Maxl][Maxn],d[Maxn];
 20 double a[Maxn][Maxn];
 21 
 22 struct node
 23 {
 24     int x,y,next;
 25 }t[Maxm*2];
 26 int len,first[Maxn];
 27 
 28 void ins(int x,int y)
 29 {
 30     t[++len].x=x;t[len].y=y;
 31     t[len].next=first[x];first[x]=len;
 32     d[x]++;
 33 }
 34 
 35 int n;
 36 struct hp
 37 {
 38     int x;double y;
 39 }cz[Maxn][Maxn];
 40 int cnt[Maxn];
 41 void gauss()
 42 {
 43     for(int i=1;i<=n;i++) cnt[i]=0;
 44     for(int i=1;i<=n;i++)
 45      for(int j=i+1;j<=n;j++)
 46      {
 47         if(dcmp(a[j][i]))
 48         {
 49             double t=a[j][i]/a[i][i];
 50             for(int k=1;k<=n;k++) a[j][k]-=a[i][k]*t;
 51             cz[j][++cnt[j]].x=i;cz[j][cnt[j]].y=t;
 52         }
 53      }
 54 }
 55 
 56 double b[Maxn];
 57 void ffind(int id)
 58 {
 59     for(int i=n;i>=1;i--)
 60     {
 61         for(int j=i+1;j<=n;j++) b[i]-=f[id][j]*a[i][j];
 62         f[id][i]=b[i]/a[i][i];
 63     }
 64 }
 65 
 66 int main()
 67 {
 68     int m,hp;
 69     scanf("%d%d%d",&n,&m,&hp);
 70     for(int i=1;i<=n;i++) scanf("%d",&ls[i]);
 71     len=0;
 72     memset(first,0,sizeof(first));
 73     memset(d,0,sizeof(d));
 74     for(int i=1;i<=m;i++)
 75     {
 76         int x,y;
 77         scanf("%d%d",&x,&y);
 78         ins(x,y);
 79         if(x!=y) ins(y,x);
 80     }
 81     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=0;
 82     for(int i=1;i<=n;i++) a[i][i]=1.0;
 83      
 84     for(int i=1;i<=n;i++)
 85     {
 86         if(ls[i]) continue;
 87         for(int j=first[i];j;j=t[j].next)
 88         {
 89             int y=t[j].y;
 90             if(y!=n) a[i][y]-=1.0/d[y];
 91         }
 92     }
 93     gauss();
 94     for(int i=hp;i>=1;i--)
 95     {
 96         for(int j=1;j<=n;j++) b[j]=0;
 97         if(i==hp) b[1]=1.0;
 98         for(int j=1;j<=n;j++) if(ls[j]&&i+ls[j]<=hp)
 99         {
100             for(int k=first[j];k;k=t[k].next)
101             {
102                 int y=t[k].y;
103                 if(y!=n) b[j]+=f[ls[j]+i][y]*1.0/d[y];
104             }
105         }
106         for(int j=1;j<=n;j++)
107          for(int k=cnt[j];k>=1;k--)
108          {
109              b[j]-=b[cz[j][k].x]*cz[j][k].y;
110          }
111         ffind(i);
112     }
113     double ans=0;
114     for(int i=1;i<=hp;i++) ans+=f[i][n];
115     printf("%.8lf
",ans);
116     return 0;
117 }
View Code

2017-04-21 14:40:22

原文地址:https://www.cnblogs.com/Konjakmoyu/p/6743520.html