过掉了讨论区的hack数据但还是wa#8

P2455 [SDOI2006] 线性方程组

PMZG @ 2021-05-11 16:22:13

思路是判定非唯一解时往后面列消元,和第一篇题解相似

#include <bits/stdc++.h>
using namespace std;
double a[55][55],b[55],c[55];
double exs=1e-8;
bool pd(double x,double y)
{
    if(x<y)swap(x,y);
    if((x-y)<exs)return 1;
    return 0;
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
         scanf("%lf",&a[i][j]);
        scanf("%lf",&b[i]);
    }
    for(int i=1;i<=n;i++)
    {
      int p=i;
      while(pd(a[i][p],0))
      {
        if(p>n)break;
        int j=i+1;
        while(pd(a[j][p],0)&&j<=n)j++;
        if(j>n){p++;continue;}
        for(int k=p;k<=n;k++)swap(a[i][k],a[j][k]);
        swap(b[i],b[j]);
      }
      for(int j=i+1;j<=n;j++)
      {
        double pp=a[j][p]/a[i][p];
        for(int k=p;k<=n;k++)
        a[j][k]-=pp*a[i][k];
        b[j]-=pp*b[i];
      }
    } 
    bool dj=0;
    for(int i=1;i<=n;i++)
    {
      bool p=0;
      for(int j=1;j<=n;j++)
      if(a[i][j])p=1;
      if(!p)
      {
        dj=1;
        if(b[i]){cout<<-1;return 0;}
      } 
    }
    if(dj){cout<<0;return 0;}
    for(int i=n;i>=1;i--)
    {
        for(int j=n-i;j>=1;j--)
         b[i]-=a[i][n-j+1]*c[n-j+1];    
        c[i]=b[i]/a[i][i];
    }
    for(int i=1;i<=n;i++)
    {
        printf("x%d=",i);
        printf("%.2lf\n",c[i]); 
    }
    return 0; 
}

by YksKuusiTAlv @ 2021-05-11 16:33:40

推荐加入随机化,因为有些数据真的可以卡掉高斯消元

void rands(){ 
    srand( time ( NULL ) ) ;
    for( R i = 1 ; i <= n - 1 ; i ++ )
    for( R j = i + 1 ; j <= n ; j ++ )
        if( rand() & 1 ) swap( m [i] , m [j] ) ;    
}

|