Luogu P5027 【Barracuda】（高斯消元）

祭一下第一道独立做出来的高斯消元(虽然在各大佬看来都是水题...)

首先这道题给了你n+1个一次方程，n个未知数

其中有一个方程是错误的

求解在合法的前提下最大的未知数是多少...

显然高斯消元...

关注到\(n≤100\)所以\(n^4\)的算法是极限

高斯消元复杂度是\(n^3\)所以我们可以暴力枚举那个方程是错误的

之后判断合法性即可...

总之也不是很难啊，关键是不要忘记illegal...刚开始程序末尾的illegal忘了然后就Subtask2 WA了一个点...

直接看代码直观一点呢

#include<cstdio>
#include<iostream>
#include<cstring> 
#include<cmath>
#define writeln(x)  write(x),puts("")
#define writep(x)   write(x),putchar(' ')
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}const double eps=1e-11; 
int n,w[105],p[105][105],tot,ANS,lst[105],lst_ans;
double a[105][105],ans[105];
inline void cmax(int &a,int b){if(a<b) a=b;}
inline void Gauss(){//高斯消元+回代 
    for(int maxn,i=1;i<=n;i++){
        maxn=i;
        for(int j=i+1;j<=n;j++) if(fabs(a[maxn][i])<fabs(a[j][i])) maxn=j;
        swap(a[maxn],a[i]);
        double div=a[i][i];
        for(int j=i;j<=n;j++) a[i][j]/=div;
        for(int j=i+1;j<=n;j++){
            div=a[j][i];
            for(int k=i;k<=n+1;k++) a[j][k]-=div*a[i][k];
        }
    }ans[n]=a[n][n+1];
    for(int i=n-1;i>=1;--i){
        ans[i]=a[i][n+1];
        for(int j=i+1;j<=n;j++)
            ans[i]-=a[i][j]*ans[j];
    }
}
int main(){
    n=read();
    for(int i=1,t;i<=n+1;i++){
        t=p[i][0]=read();
        for(int j=1;j<=t;j++)   p[i][j]=read();
        w[i]=read();
    }int ppp=0;
    for(int wr=1;wr<=n+1;wr++){//第wr(ong)次出现错误答案
        tot=0;memset(a,0,sizeof(a));
        for(int i=1;i<=n+1;i++)
            if(i!=wr){
                ++tot,a[tot][n+1]=w[i];
                for(int j=1;j<=p[i][0];j++)a[tot][p[i][j]]=1;
            }
        Gauss();//构造方程+高斯消元
//------------------------------------------------------------------------      
        ANS=0;tot=0;int ff=0;
        for(int i=1;i<=n;i++){
            int flag=0;
            for(int j=1;j<=n;j++)
                if(fabs(a[i][j])>eps) flag=1;
            if(flag==0) {ff=1;break;}
        }if(ff) continue;//检查1_唯一解
//------------------------------------------------------------------------      
        for(int i=1;i<=n;i++)   
            if(fabs(ans[i]-(int)ans[i])<eps&&ans[i]>0)  
                lst[i]=(int)ans[i]; 
            else    {ff=1;break;}//检查2_整数
        if(ff) continue;
        for(int i=1;i<=n;i++)   cmax(ANS,lst[i]);
        for(int i=1;i<=n;i++)   if(ans[i]==ANS) ++tot,ff=i;//检查3_最大值唯一
        if(tot>1)   continue;
//------------------------------------------------------------------------
        if(ppp){puts("illegal");return 0;}//多种可能方案 
        lst_ans=ff;ppp=1;
    }
    if(!ppp) puts("illegal");//没有可能方案 
    else writeln(lst_ans);
    return 0;
}