洛谷 P5027 Barracuda（高斯消元）
题目链接 Barracuda
题目背景
小正方形的冒险旅途，并不顺利。
一路上，小正方形看到了壮美秀丽的小岛被污染，看到了雄伟壮观的火山，还碰到了许许多多的敌人。
眼下，小正方形正在对付一个巨大的三角形。
题目描述
大三角形给小正方形讲起自己的过去：过去的它是一个挖宝工，后来被黑暗之主污染才会落到此番境地。
它也希望小正方形去战胜黑暗之主，不过限于黑暗之主的眼线密布，因此必须给小正方形设置障碍才能骗过那些“眼线”。
他给小正方形的问题是：它有
n
n
n个小三角形，每个小三角形有一定的质量，它对这些三角形进行了
n
+
1
n + 1
n+1次称量，然而由于托盘天平(?)的问题，有一次称量的结果是有误的。
现在，大三角形想要知道最重的小三角形的 编号。
一组输入是合法的，当且仅当输入满足以下条件：
不存在一组
i
,
j
i,j
i,j，使得当我们假定第
i
i
i 条称量数据有误时能求出一种合法方案且我们假定第
j
j
j 条称量数据有误时也能求出一种合法方案。
合法方案定义如下：
1、最重的三角形只有一个。
2、不存在重量不确定的三角形。
3、所有三角形的重量均为正整数。
输入格式
输入的第一行为一个正整数
n
n
n，表示小三角形的数目。
接下来
n
+
1
n + 1
n+1 行，每行按照以下格式输入：
首先是一个正整数
m
m
m，表示这次称量抓了几个小三角形。
接下来
m
m
m 个整数，表示称量的小三角形的编号。
最后一个整数
w
e
i
g
h
t
weight
weight ，表示这次称量的结果。
输出格式
若合法，输出最重小三角形的编号，否则输出 “illegal”(不含引号)。
输入输出样例
输入 #1
2
1 1 2
2 1 2 5
2 1 2 1
输出 #1
2
输入 #2
2
1 1 2
2 1 2 4
2 1 2 5
输出 #2
2
输入 #3
2
1 1 2
2 1 2 6
2 1 2 5
输出 #3
illegal
说明/提示
样例一：
若第一次称量结果错误，则无法得出正确解。
若第二次称量结果错误，则第二个小三角形重量为负，显然不对。
若第三次称量结果错误，我们得出
1
1
1 号小三角形重量为
2
2
2，
2
2
2号小三角形重量为
3
3
3，
2
2
2号小三角形最重。
本题采用捆绑测试，共有三个
s
u
b
t
a
s
k
subtask
subtask，描述如下：
s
u
b
t
a
s
k
0
−
30
P
t
s
subtask 0−30Pts
subtask0−30Pts 保证小三角形的重量 <= 20且
n
<
=
5
n <= 5
n<=5，在这个 subtasksubtask 中，你每通过一个点可获得 1010 分。
s u b t a s k 1 − 30 P t s subtask 1 - 30Pts subtask1−30Pts 保证小三角形的重量 <= 100 并且 n < = 100 n <= 100 n<=100，数据为随机生成。
s u b t a s k 2 − 40 P t s subtask 2 - 40Pts subtask2−40Pts 保证小三角形的重量 <= 100 并且 n < = 100 n <= 100 n<=100
在后两个 s u b t a s k subtask subtask 中，你必须通过所有数据才能得分。
对于 100 % 100\% 100% 的数据， 1 < = m < = n 1 1 <= m <= n1 1<=m<=n1
题目思路
这是一道典型的高斯消元题目，首先，本题n<=100，而高斯消元
O
(
n
3
)
\mathrm O\!\left(n^3\right)
O(n3) ，如果首先可以枚举错误方程，每次高消跑一遍，
O
(
n
4
)
\mathrm O\!\left(n^4\right)
O(n4)
) 其中
n
≤
n\leq
n≤ 100，是过得去的。
这道题的细节处理很多，由题意可以得出这样几个无解情况：
1.判断答案是否为正整数
2.是否有多个最重三角形
3.重量不确定，即有多种删掉一个式子的情况合法
代码
/*************************************************
Note:
*************************************************/
#include <queue>
#include <stack>
#include <set>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int eps = 1e-6;
inline int read()
{
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
double a[150][150];
double b[150][150];
int n, m, x;
int maxx, pre;
int gauss()
{
int c, r;
for (c = 1, r = 1; c <= n; c++)
{
int t = r;
for (int i = r; i < n; i++)
{
if (fabs(a[t][c]) < fabs(a[i][c]))
t = i;
}
if (fabs(a[t][c]) < eps)
return 0;
for (int i = c; i <= n + 1; i++)
swap(a[r][i], a[t][i]);
for (int i = n + 1; i >= c; i--)
a[r][i] /= a[r][c];
for (int i = r + 1; i <= n; i++)
{
if (fabs(a[i][c]) >= eps)
{
for (int j = n + 1; j >= c; j--)
a[i][j] -= a[r][j] * a[i][c];
}
}
r++;
}
//高斯消元模板
for (int i = n; i >= 1; i--)
{
for (int j = i + 1; j <= n; j++)
{
a[i][n + 1] -= a[j][n + 1] * a[i][j];
}
if (a[i][n + 1] < eps || ((int)a[i][n + 1]) < a[i][n + 1])
return 0;
}
int sum;
maxx = -1;
for (int i = 1; i <= n; i++)
{
if ((int)a[i][n + 1] > maxx)
maxx = a[i][n + 1], sum = i;
}
int num = 0;
for (int i = 1; i <= n; i++)
{
if ((int)a[i][n + 1] == maxx)
num++;
}
if (num > 1)
return 0;
return sum;
}
int tot;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n + 1; i++)
{
scanf("%d", &m);
for (int j = 1; j <= m; j++)
{
scanf("%d", &x);
b[i][x]++;
}
scanf("%d", &x);
b[i][n + 1] = x * 1.0;
}
for (int i = 1; i <= n + 1; i++)
{
int cnt = 0;
for (int h = 1; h <= n + 1; h++)
{
if (h == i)
continue;
cnt++;
for (int k = 1; k <= n + 1; k++)
{
a[cnt][k] = b[h][k];
}
}
int p = gauss();
if (p == 0)
continue;
else
tot++, pre = p;
}
if (tot > 1 || tot == 0)
puts("illegal");
else
cout << pre;
return 0;
}