2 条题解

  • 0
    @ 2025-10-8 16:58:37
    #include <bits/stdc++.h> 
    using namespace std;
    const int N=310;
    const double eps=1e-9;
    int n,m;double p,q;
    bool mp[N][N];
    int d[N];
    double a[N][N],x[N];
    void gauss()
    {
        for(int i=1;i<=n;++i)
        {
            int r=i;for(int j=i+1;j<=n;++j)if(fabs(a[r][i])<fabs(a[j][i]))r=j;
            if(r!=i)swap(a[i],a[r]);
            
            for(int j=1;j<=n;++j)if(j!=i)
            {
                double bs=a[j][i]/a[i][i];
                for(int k=i;k<=n+1;++k)a[j][k]-=a[i][k]*bs;
            }
        }
        for(int i=1;i<=n;++i)x[i]=a[i][n+1]/a[i][i];
    	for(int i=1;i<=n;i++)printf("%.9lf\n",x[i]);
    }
    int main()
    {
        scanf("%d%d%lf%lf",&n,&m,&p,&q);
        memset(mp,0,sizeof(mp));
        memset(d,0,sizeof(d));
        for(int i=1,x,y;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            mp[x][y]=mp[y][x]=True;
            d[x]++;d[y]++;
        }
        memset(a,0,sizeof(a));
        a[1][n+1]=p/q;
        for(int i=1;i<=n;i++)
        {
            a[i][i]=1;
            for(int j=1;j<=n;j++)
                if(mp[i][j])
                    a[i][j]=-(1.0-p/q)/d[j];
        }
        gauss();
        return 0;
    }
    

    • 0
      @ 2025-10-8 16:58:25
      #include<bits/stdc++.h> 
      using namespace std;
      const int N=310;
      const double eps=1e-9;
      int n,m;double p,q;
      bool mp[N][N];
      int d[N];
      double a[N][N],x[N];
      void gauss()
      {
          for(int i=1;i<=n;++i)
          {
              int r=i;for(int j=i+1;j<=n;++j)if(fabs(a[r][i])<fabs(a[j][i]))r=j;
              if(r!=i)swap(a[i],a[r]);
              
              for(int j=1;j<=n;++j)if(j!=i)
              {
                  double bs=a[j][i]/a[i][i];
                  for(int k=i;k<=n+1;++k)a[j][k]-=a[i][k]*bs;
              }
          }
          for(int i=1;i<=n;++i)x[i]=a[i][n+1]/a[i][i];
      	for(int i=1;i<=n;i++)printf("%.9lf\n",x[i]);
      }
      int main()
      {
          scanf("%d%d%lf%lf",&n,&m,&p,&q);
          memset(mp,0,sizeof(mp));
          memset(d,0,sizeof(d));
          for(int i=1,x,y;i<=m;i++)
          {
              scanf("%d%d",&x,&y);
              mp[x][y]=mp[y][x]=True;
              d[x]++;d[y]++;
          }
          memset(a,0,sizeof(a));
          a[1][n+1]=p/q;
          for(int i=1;i<=n;i++)
          {
              a[i][i]=1;
              for(int j=1;j<=n;j++)
                  if(mp[i][j])
                      a[i][j]=-(1.0-p/q)/d[j];
          }
          gauss();
          return 0;
      }

      • 1

      *【高斯消元】无向图中炸弹爆炸的概率[USACO10HOL] Driving Out the Piggies G(spj)(好题

      信息

      ID
      1792
      时间
      1000ms
      内存
      128MiB
      难度
      9
      标签
      递交数
      34
      已通过
      4
      上传者