题解 P5027 【Barracuda】

· · 题解

高斯消元的板题

题意

给出 n + 1 多元一次方程，共 n 个未知量，其中有一个是错误的方程，现在需要你把正确方程组中解最大的编号输出

思路

首先考虑如何构造方程矩阵，对于每一行的输入，都对这个编号在方程中的系数则都为 1 ，其他全为 0 ，所以显然方程系数不会超过 1

然后可以枚举这 n + 1 个方程中的某一个为错误的，如果发现多解或无解则这次枚举出的矩阵不是正确的，最终输出包含唯一解的矩阵中解最大的编号，如果枚举发现没有这样的矩阵，则输出 illegal

具体实现看代码

代码

#include <iostream>
#include <cmath>
#include <cstdio>
#define eps 1e-7
#define MAX_N 1010
using namespace std;
double c[MAX_N][MAX_N],b[MAX_N];
int n;
bool integer(double s){
    if(abs(round(s) - s) < eps) 
        return true;
    return false;
}
int Gauss(int kill){
    double c2[MAX_N][MAX_N],b2[MAX_N];
    int t = 0;
    for(int i = 1;i <= n + 1;i++){
        if(kill == i)continue;
        t++;
        for(int j = 1;j <= n;j++)
            c2[t][j] = c[i][j];
        b2[t] = b[i];
    }
    double rate;
    for(int i = 1;i <= n;i++){
        for(int j = i;j <= n;j++)
            if(fabs(c2[j][i]) > 1e-8)
                swap(c2[i],c2[j]),swap(b2[i],b2[j]);
        if(c2[i][i] == 0)
            return -1;
        for(int j = 1;j <= n;j++){
            if(i == j)continue;
            rate = c2[j][i] / c2[i][i];
            for(int k = i;k <= n;k++)
                c2[j][k] -= c2[i][k] * rate;
            b2[j] -= b2[i] * rate;
        }
    }
    int maxn = -1,maxt = 0,maxs = -1;
    for(int i = 1;i <= n;i++){
        double ans = b2[i] / c2[i][i];
        if(ans < 0 || integer(ans) == false)return -1;
        if(ans > maxn)maxn = ans,maxt = 1,maxs = i;
        else if(ans == maxn)maxt++;
    }
    if(maxt != 1)return -1;
    return maxs;
}
int main(){
    cin >> n;
    for(int i = 1;i <= n + 1;i++){
        int m;
        cin >> m;
        while(m--){
            int x;
            cin >> x;
            c[i][x] = 1;
        }
        cin >> b[i];
    }
    int t = 0,ans = -1;
    for(int i = 1;i <= n + 1;i++){
        int x = Gauss(i);
        if(x != -1){
            ans = x;
            t++;
        }
    }
    if(t != 1){
        cout << "illegal" << endl;
        return 0;
    } 
    cout << ans << endl;
    return 0;
}

后记