对偶问题相关
1.一些定义
其中(c)表示每种产品可以得到的收益，(x)是每种产品的生产个数。(A)是每种产品需要的每种原材料的个数，(b)是每种原材料的个数限制。(y)是每种原材料的价格。
那么这个式子左侧就是一个生产商，有若干原材料，需要找到生产产品的最优方案，使得收益最大化。
右侧是一个黑心商家，有这么多原材料要出售，生产每种产品的原材料的价钱不能低于其出售的收益，也就是不想让生产商赚钱，但是为了让自己体面一点，想要原材料卖出去的总价钱最少。
那都说了不想让生产商赚钱，那么在此基础上又想要原材料的总价格最小，显然就是生产出来不赔不赚。
意味着左右两侧是相等的。（强行感性理解）
那么这个东西可以把最值问题转化为其对偶问题。
一个例子
有(m)个人，每个人可以花费(c_i)的代价，覆盖树上(a_i,b_i)这段路径，保证(a_i)是(b_i)的祖先。求最小代价使得每条边都被覆盖了一次。
既然是最小代价，那么此时我们处于等式的右侧，那么想想每个东西分别代表着什么。
每种产品和(m)个人一一对应，树上的每一条边和一个原材料进行对应，这样就知道了(A)是什么。而(y)显然就是(m)个人，每个人选还是不选。那么(b)显然就是每个人的代价，要做的就是最小化被选的人的代价之和。
(c)是出售价格，那么在题目中的限制就是每条边都至少要被覆盖一次，因此(c)全是(1)。
这样子我们确定了右边了。
现在转化对偶问题考虑左边。(x)是每个人是选还是不选，(max{c^Tx})就是所有边被覆盖总次数的最大值。
(Ax)的含义就是每个人覆盖的区间中，所有边被覆盖的总次数，它要小于这个人选择的代价。
那么这样子就转化出来了对偶问题：
给定一棵树，每条边可以被标记若干次，有若干个限制，每次限制一条链上所有边被覆盖的总次数不能超过一个给定值，现在要最大化边被覆盖的总次数。
原问题似乎并没有那么好解决，但是对偶问题可以很容易的使用贪心解决。