这是一道模板题。
(这个题现在标程挂了。。哪位哥哥愿意提供一下靠谱的标程呀?) 现在的新标程有没有问题啊? 现在的新标程有没有问题啊?
已将所有ex tests的t改成1。现在的checker会先判解是否合法,再判和标准答案的误差。如果发现有std优的合法解,请联系管理员。
本题中你需要求解一个标准型线性规划:
有 $n$ 个实数变量 $x_1,x_2,\dots,x_n$ 和 $m$ 条约束,其中第 $i$ 条约束形如 $\sum_{j=1}^n a_{ij}x_j \le b_i$。
此外这 $n$ 个变量需要满足非负性限制,即 $x_j\ge 0$。
在满足上述所有条件的情况下,你需要指定每个变量 $x_j$ 的取值,使得目标函数 $F=\sum_{j=1}^n c_j x_j$ 的值最大。
输入格式
第一行三个正整数 $n,m,t$。其中 $t \in \{0,1\}$。
第二行有 $n$ 个整数 $c_1,c_2,\cdots,c_n$,整数间均用一个空格分隔。
接下来 $m$ 行,每行代表一条约束,其中第 $i$ 行有 $n+1$ 个整数 $a_{i1},a_{i2},\cdots,a_{in}, b_i$,整数间均用一个空格分隔。
输出格式
如果不存在满足所有约束的解,仅输出一行 "Infeasible"。
如果对于任意的 $M$,都存在一组解使得目标函数的值大于 $M$,仅输出一行"Unbounded"。
否则,第一行输出一个实数,表示目标函数的最大值 $F$。当第一行与标准答案的相对误差或绝对误差不超过 $10^{-6}$,你的答案被判为正确。
如果 $t=1$,那么你还需要输出第二行,用空格隔开的 $n$ 个非负实数,表示此时 $x_1,x_2,\dots,x_n$ 的取值,如有多组方案请任意输出其中一个。
判断第二行是否合法时,我们首先检验 $F-\sum_{j=1}^n c_j x_j$ 是否为 $0$,再对于所有 $i$,检验 $\min\{ 0,b_i-\sum_{j=1}^n a_{ij}x_j \}$ 是否为 $0$。检验时我们会将其中大于 $0$ 的项和不大于 $0$ 的项的绝对值分别相加得到 $S_+$ 和 $S_-$,如果 $S_+$ 和 $S_-$ 的相对误差或绝对误差不超过 $10^{-6}$,则判为正确。
如果 $t=0$,或者出现 Infeasible 或 Unbounded 时,不需要输出第二行。
样例一
input
2 2 1 1 1 2 1 6 -1 2 3
output
4.2 1.8 2.4
explanation
两条约束分别为 $2x_1+x_2\le 6,-x_1+2x_2\le 3$。
当 $x_1=1.8,x_2=2.4$ 时目标函数 $x_1+x_2$ 取到最大值 $4.2$。
样例二
input
2 2 1 1 -1 1 1 4 -1 -2 -2
output
4.0 4.0 0.0
explanation
注意 $x_j\ge 0$ 的限制。
样例三
input
3 3 1 0 0 1 -2 1 0 -4 1 1 0 4 1 -2 0 -4
output
Infeasible
样例四
input
2 1 1 0 1 1 0 1
output
Unbounded
限制与约定
对于所有数据,$1\leq n,m \leq 20$,$0 \leq |a_{ij}|,|b_i|,|c_j|\leq 100$,$t \in \{0,1\}$。
本题包含 4 个子任务,每个 25 分。
子任务 1,3 满足 $b_i\ge 0$。
子任务 2,4 没有特殊限制。
子任务 1,2 中 $t=0$。
子任务 3,4 中 $t=1$。
时间限制:$1\texttt{s}$
空间限制:$256\texttt{MB}$