logo AlgoBeat OnlineJudge
登录 注册

#213420. 【模板】线性规划

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

本题中你需要求解一个标准型线性规划:

个实数变量 条约束,其中第 条约束形如

此外这 个变量需要满足非负性限制,即

在满足上述所有条件的情况下,你需要指定每个变量 的取值,使得目标函数 的值最大。

保证数据随机。

输入格式

第一行两个正整数

第二行有 个整数 ,整数间均用一个空格分隔。

接下来 行,每行代表一条约束,其中第 行有 个整数 ,整数间均用一个空格分隔。

输出格式

如果不存在满足所有约束的解,仅输出一行 Infeasible

如果对于任意的 ,都存在一组解使得目标函数的值大于 ,仅输出一行 Unbounded

否则,第一行输出一个实数,表示目标函数的最大值 。当第一行与标准答案的相对误差或绝对误差不超过 ,你的答案被判为正确。

第二行输出用空格隔开的 个非负实数,表示此时 的取值,如有多组方案请任意输出其中一个。

判断第二行是否合法时,我们首先检验 的相对误差或绝对误差不超过 ,再对于所有 ,检验 的相对误差或绝对误差不超过 。若均满足,则判为正确。

如果出现 InfeasibleUnbounded 时,不需要输出第二行。

样例

样例输入 1

2 2
1 1
2 1 6
-1 2 3

样例输出 1

4.2
1.8 2.4

样例输入 2

2 2
1 -1
1 1 4
-1 -2 -2

样例输出 2

4.0
4.0 0.0

样例输入 3

3 3
0 0 1
-2 1 0 -4
1 1 0 4
1 -2 0 -4

样例输出 3

Infeasible

样例输入 4

2 1
0 1
1 0 1

样例输出 4

Unbounded

数据范围与提示

数据范围

对于所有数据,。保证数据随机。

子任务编号 特殊性质 分值
1
2
3
4
5