题解 洛谷P5027 【Barracuda】(高斯消元)

题面:

题目背景

小正方形的冒险旅途,并不顺利。

一路上,小正方形看到了壮美秀丽的小岛被污染,看到了雄伟壮观的火山,还碰到了许许多多的敌人。

眼下,小正方形正在对付一个巨大的三角形。

题目描述

大三角形给小正方形讲起自己的过去:过去的它是一个挖宝工,后来被黑暗之主污染才会落到此番境地。

它也希望小正方形去战胜黑暗之主,不过限于黑暗之主的眼线密布,因此必须给小正方形设置障碍才能骗过那些“眼线”。

他给小正方形的问题是:它有 nn 个小三角形,每个小三角形有一定的质量,它对这些三角形进行了 n + 1n+1次称量,然而由于托盘天平(?)的问题,有一次称量的结果是有误的。

现在,大三角形想要知道最重的小三角形的 编号。

一组输入是合法的,当且仅当输入满足以下条件:

不存在一组 ii,jj,使得当我们假定第 ii 条称量数据有误时能求出一种合法方案且我们假定第 jj 条称量数据有误时也能求出一种合法方案。

合法方案定义如下:

1、最重的三角形只有一个。

2、不存在重量不确定的三角形。

3、所有三角形的重量均为正整数。

输入格式

输入的第一行为一个正整数 nn,表示小三角形的数目。

接下来 n + 1n+1 行,每行按照以下格式输入:

首先是一个正整数 mm,表示这次称量抓了几个小三角形。

接下来 mm 个整数,表示称量的小三角形的编号。

最后一个整数 weightweight ,表示这次称量的结果。

输出格式

若合法,输出最重小三角形的编号,否则输出 "illegal"(不含引号)。


 

因为这道题很有趣 (其实是我毒了13遍才过) ,同时也为了写给自己供复习,于是决定写篇题解
首先,本题n<=100,而高斯消元n^3,如果暴力枚举错误的式子就是n^4,是卡得过去的
这道题的细节处理很多,由题意可以得出这样几个无解情况
1.判断答案是否为正整数
2.是否有多个最重三角形
3.重量不确定,即有多种删掉一个式子的情况合法
于是,上代码 (不喜勿喷)

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n;
int a[105][105];
double b[105][105];
int ans;
int ansbj; 
int Gauss()
{
    for(int i=1;i<=n;i++)
    {
        int no=i;
        for(int j=i+1;j<=n;j++)if(abs(b[j][i])>abs(b[no][i]))no=j;
        for(int j=1;j<=n+1;j++)swap(b[i][j],b[no][j]);
        double x=b[i][i];
        for(int j=i;j<=n+1;j++)b[i][j]/=x;
        for(int j=1;j<=n;j++)
        {
            double y=b[j][i];
            for(int k=1;k<=n+1;k++)
            if(i!=j)
            b[j][k]-=y*b[i][k];
        }
    }//高斯消元模版,此时第i个未知数的解存在b[i][n+1]中 
    int num;
    for(int i=1;i<=n;i++)
    {
        num=0;
        for(int j=1;j<=n+1;j++)if(!b[i][j])num++;
        if(num==n+1)return 0;//全为0,无数解 
    }
    for(int i=1;i<=n;i++)if(b[i][n+1]<=0)return 0;//是否为正数 
    for(int i=1;i<=n;i++)if(b[i][n+1]!=(int)b[i][n+1])return 0;//是否为整数 
    double maxx=-0x3f3f3f3f;int bjbj=0;
    for(int i=1;i<=n;i++)maxx=max(maxx,b[i][n+1]);//求出最重三角形 
    for(int i=1;i<=n;i++)if(b[i][n+1]==maxx){if(bjbj)return 0;maxx=b[i][n+1];bjbj=i;}//判断是否有多个最重三角形
    //如果到这里还没有return就说明答案合法 
    return bjbj;//返回最重三角形的编号 
}
int main()
{
    int k,x;
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&x);
            a[i][x]=1;
        }
        scanf("%d",&a[i][n+1]);
    }
    for(int i=1;i<=n+1;i++)
    {
        swap(a[i],a[n+1]);//把错的式子换到第n+1行 
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n+1;k++)b[j][k]=a[j][k];//将删去错误式子的矩阵存在b中 
        swap(a[i],a[n+1]);//换回去
        int nobj=Gauss();//判断是否合法 
        if(nobj)
        {
            if(ansbj){printf("illegal");return 0;}//有多种情况合法 
            ans=nobj;ansbj=1;//
        }
    }
    if(!ansbj)printf("illegal");else printf("%d",ans);//判断是否有合法结果 
    return 0;
}

  

上一篇:洛谷 P1101单词方阵


下一篇:AtCoder Regular Contest 105-C