uva-10828 期望dp+gauss

浅浅的花香味﹌ 2022-05-09 11:08 260阅读 0赞

传送门

题意：给你一个有向图，从1号节点出发，问经过某个点的期望次数。

思路：传递闭包写错wa到哭。设 dp[i]为经过i点期望

dp[v]=dp[u1]*p1+dp[u2]*p2+….（对于第一个点应该再+1）

将每个dp看做变量，就可以构成n*n的矩阵比如样例1构成矩阵如下

-1 1 0 -1

0.5 -1 0 0

0 0.5 -1 0

用高斯消元解就可以，对于有解得dp直接输出就可以，对于无穷的，与他相关的点也无穷，也就是他传递闭包能到的点。

代码一：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define eps 1e-9
  4. const int MAXN=110;
  5. double a[MAXN][MAXN], x[MAXN];
  6. int equ, var;
  7. int n;
  9. int gauss(){
  10.     int i, j, k, col, max_r;
  11.     for(k=0, col=0; k<equ&&col<var; k++, col++){
  12.         max_r=k;
  13.         for(i=k+1; i<equ; i++)
  14.             if(fabs(a[i][col])>fabs(a[max_r][col]))
  15.                 max_r=i;
  17.         if(fabs(a[max_r][col])<eps) return 0;
  18.         if(k!=max_r){
  19.             for(j=col; j<var; j++)
  20.                 swap(a[k][j], a[max_r][j]);
  21.             swap(x[k], x[max_r]);
  22.         }
  23.         x[k]/=a[k][col];
  24.         for(j=col+1; j<var; j++) a[k][j]/=a[k][col];
  25.         a[k][col]=1;
  26.         for(i=0;i<equ; i++)
  27.         if(i!=k){
  28.             x[i]-=x[k]*a[i][col];
  29.             for(j=col+1; j<var; j++) a[i][j]-=a[k][j]*a[i][col];
  30.             a[i][col]=0;
  31.         }
  32.     }
  35.     return 0;
  36. }
  38. vector<int> G[110];
  39. int dgr[110];
  40. bitset<110> inf;
  41. int mp[110][110];
  43. int main(){
  44.     int cas=0;
  46.     while(~scanf("%d", &n) && n){
  47.         memset(a, 0, sizeof a);
  48.         memset(x, 0, sizeof x);
  49.         memset(mp, 0, sizeof mp);
  50.         inf.reset();
  52.         for(int i=0; i<n; i++)
  53.             G[i].clear(), dgr[i]=0, a[i][i]=-1;
  54.         int u, v;
  55.         while(scanf("%d%d", &u, &v)&&(u||v)){
  56.             u--; v--;
  57.             G[u].push_back(v);
  58.             mp[u][v]=1;
  59.             dgr[u]++;
  60.         }
  61.         equ=n, var=n;
  62.         x[0]=-1;
  63.         for(int i=0; i<n; i++){
  64.             for(int j=0; j<G[i].size(); j++){
  65.                 int v=G[i][j];
  66.                 a[v][i]+=1./dgr[i];
  67.             }
  68.         }
  70.         for(int k=0; k<n; k++)
  71.             for(int i=0; i<n; i++)
  72.                 for(int j=0; j<n; j++)
  73.                     if(mp[i][k] && mp[k][j]) mp[i][j]=1;
  75.         gauss();
  77.         for(int i=0; i<n; i++){
  78.             if(fabs(x[i])>eps && fabs(a[i][i])<eps) inf[i]=1;
  80.             if(inf[i])
  81.             for(int j=0; j<n; j++)
  82.                 if(mp[i][j]) inf[j]=inf[i];
  83.         }
  85.         printf("Case #%d:\n", ++cas);
  86.         int Q, p;
  87.         scanf("%d", &Q);
  88.         while(Q--){
  89.             scanf("%d", &p);
  90.             p--;
  91.             if(inf[p])
  92.                 puts("infinity");
  93.             else{
  94.                 printf("%.3lf\n", fabs(x[p]));
  95.             }
  96.         }
  98.     }
  100.     return 0;
  101. }

代码二：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define eps 1e-9
  4. const int MAXN=110;
  5. double a[MAXN][MAXN], x[MAXN];
  6. int equ, var;
  7. int n;
  9. int gauss(){
  10.     int i, j, k, col, max_r;
  11.     for(k=0, col=0; k<equ&&col<var; k++, col++){
  12.         max_r=k;
  13.         for(i=k+1; i<equ; i++)
  14.             if(fabs(a[i][col])>fabs(a[max_r][col]))
  15.                 max_r=i;
  17.         if(fabs(a[max_r][col])<eps) return 0;
  18.         if(k!=max_r){
  19.             for(j=col; j<var; j++)
  20.                 swap(a[k][j], a[max_r][j]);
  21.             swap(x[k], x[max_r]);
  22.         }
  23.         x[k]/=a[k][col];
  24.         for(j=col+1; j<var; j++) a[k][j]/=a[k][col];
  25.         a[k][col]=1;
  26.         for(i=0;i<equ; i++)
  27.         if(i!=k){
  28.             x[i]-=x[k]*a[i][col];
  29.             for(j=col+1; j<var; j++) a[i][j]-=a[k][j]*a[i][col];
  30.             a[i][col]=0;
  31.         }
  32.     }
  35.     return 0;
  36. }
  38. vector<int> G[110];
  39. int dgr[110];
  40. bitset<110> inf;
  42. int main(){
  43.     int cas=0;
  44.     //freopen("E:/in.txt", "r", stdin);
  45.     //freopen("E:/example.txt", "w", stdout);
  46.     while(~scanf("%d", &n) && n){
  47.         memset(a, 0, sizeof a);
  48.         memset(x, 0, sizeof x);
  49.         inf.reset();
  51.         for(int i=0; i<n; i++)
  52.             G[i].clear(), dgr[i]=0, a[i][i]=-1;
  53.         int u, v;
  54.         while(scanf("%d%d", &u, &v)&&(u||v)){
  55.             u--; v--;
  56.             G[u].push_back(v);
  57.             dgr[u]++;
  58.         }
  59.         equ=n, var=n;
  60.         x[0]=-1;
  61.         for(int i=0; i<n; i++){
  62.             for(int j=0; j<G[i].size(); j++){
  63.                 int v=G[i][j];
  64.                 a[v][i]+=1./dgr[i];
  65.             }
  66.         }
  67.         gauss();
  69.         for(int i=n-1; i>=0; i--){
  70.             if(fabs(x[i])>eps && fabs(a[i][i])<eps) inf[i]=1;
  71.             for(int j=i+1; j<n; j++) if(fabs(a[i][j])>eps && inf[j]) inf[i]=1;
  72.         }
  74.         printf("Case #%d:\n", ++cas);
  75.         int Q, p;
  76.         scanf("%d", &Q);
  77.         while(Q--){
  78.             scanf("%d", &p);
  79.             p--;
  80.             if(inf[p])
  81.                 puts("infinity");
  82.             else{
  83.                 printf("%.3lf\n", fabs(x[p]));
  84.             }
  85.         }
  87.     }
  89.     return 0;
  90. }
  91. /*
  92. 3
  93. 1 3
  94. 3 2
  95. 0 0
  96. 3
  97. 1
  98. 2
  99. 3
  101. 5
  102. 1 2
  103. 3 5
  104. 2 4
  105. 3 1
  106. 4 2
  107. 2 3
  108. 4 5
  109. 0 0
  110. 5
  111. 1
  112. 2
  113. 3
  114. 4
  115. 5
  118. */

发表评论

表情：
评论列表 （有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

    相关 期望DP入门

    期望DP一般步骤： 1.模拟过程，找出线性性质，作为阶段（这本质上也是线性DP） 2.涉及DP状态 原则： 体现线性性质 体现边权 根据对期望有无贡献来设计状态

    雨点打透心脏的1/2处雨点打透心脏的1/2处/ 0 赞/ 167 阅读

    相关 期望、方差

    一、期望和方差的定义 随机变量(Random Variable) X 是一个映射，把随机试验的结果与实数建立起了一一对应的关系。而期望与方差是随机变量的两个重要的数字特征

    亦凉亦凉/ 0 赞/ 133 阅读

    相关 cf期望概率专题

    cf1009E：求到第i段期望和的比较困难，但是单独求每段的期望是比较容易的，所以单独对每段求和，然后累计总和 E\[i\]=1/2\a1+1/4\a2+...+1/2^(i

    傷城~傷城~/ 0 赞/ 144 阅读