P13337 【模板】线性规划

本题中你需要求解一个标准型线性规划： 有 $n$ 个实数变量 $x_1,x_2,\dots,x_n$ 和 $m$ 条约束，其中第 $i$ 条约束形如 $\sum_{j=1}^n a_{i,j}x_j \le b_i$。 此外这 $n$ 个变量需要满足非负性限制，即 $x_j\ge 0$。 在满足上述所有条件的情况下，你需要指定每个变量 $x_j$ 的取值，使得目标函数 $F=\sum_{j=1}^n c_j x_j$ 的值最大。 **保证数据随机。**

第一行两个正整数 $n,m$。 第二行有 $n$ 个整数 $c_1,c_2,\cdots,c_n$，整数间均用一个空格分隔。 接下来 $m$ 行，每行代表一条约束，其中第 $i$ 行有 $n+1$ 个整数 $a_{i,1},a_{i,2},\cdots,a_{i,n}, b_i$，整数间均用一个空格分隔。

如果不存在满足所有约束的解，仅输出一行 `Infeasible`。 如果对于任意的 $M$，都存在一组解使得目标函数的值大于 $M$，仅输出一行 `Unbounded`。 否则，第一行输出一个实数，表示目标函数的最大值 $F$。当第一行与标准答案的相对误差或绝对误差不超过 $10^{-6}$，你的答案被判为正确。 第二行输出用空格隔开的 $n$ 个非负实数，表示此时 $x_1,x_2,\dots,x_n$ 的取值，如有多组方案请任意输出其中一个。 判断第二行是否合法时，我们首先检验 $F$ 与 $\sum_{j=1}^n c_j x_j$ 的相对误差或绝对误差不超过 $10^{-6}$，再对于所有 $i$，检验 $\sum_{j=1}^n a_{i,j}x_j\le b_i$ 或 $\sum_{j=1}^n a_{i,j}x_j$ 与 $b_i$ 的相对误差或绝对误差不超过 $10^{-6}$。若均满足，则判为正确。 如果出现 `Infeasible` 或 `Unbounded` 时，不需要输出第二行。

### 数据范围 对于所有数据，$1\leq n,m \leq 100$，$0 \leq |a_{i,j}|,|b_i|,|c_j|\leq 100$。保证数据随机。 | 子任务编号 | $n,m\le $ | 特殊性质 | 分值 | | ---------- | --------- | ---------- | ---- | | 1 | $10$ | | $20$ | | 2 | $20$ | | $20$ | | 3 | $50$ | $b_i\ge 0$ | $10$ | | 4 | $50$ | | $20$ | | 5 | $100$ | | $30$ |