这个实现：
http://hi.baidu.com/__vani/item/19c2b226010fd4896e2cc345
是有问题的，只能在变量始终为0\1\-1的题里用
http://hi.baidu.com/nehzilrz/item/9fba95952db43b30336eebf7
这个通用一些……
注意各种变量的正负。
Yangff 20:23:37 …… Yangff 20:23:40 好吧&…… Yangff 20:23:43 原来是不等式。。 Yangff 20:24:21 等扥…… Yangff 20:24:23 等等…… Yangff 20:24:44 这诡异的式子。。 wyl8899 20:24:58 有什么问题吗.. wyl8899 20:25:16 recall x[i]=b[i]-∑A[i][j]*x[j] , x[i]>=0 Yangff 20:25:26 不应该是x[i+n]么。。 wyl8899 20:25:23 哦.. wyl8899 20:25:29 因为是虚拟的变量 Yangff 20:25:47 …… Yangff 20:25:50 我知道是虚拟的。。 Yangff 20:25:55 看起来直接就没存了。。 wyl8899 20:26:01 恩.. 看起来是这个样子 Yangff 20:26:10 但是移动的时候会移动到啊。。这里就完全不理解了。。 Yangff 20:26:38 = =……我觉得省略了各种的正负号变换…… Yangff 20:26:50 符号看的我快吐了。。 wyl8899 20:26:52 我也觉得.. Yangff 20:29:27 = =。。你问一下他，没有辅助变量的话……他在和谁松弛。。 Yangff 20:29:36 我是说pivot。。 wyl8899 20:30:13 这就是x[l]和x[e]的对换啊... Yangff 20:30:30 对啊。 Yangff 20:30:40 但是问题是x[l]和x[e]都是当前已选定的。。 wyl8899 20:30:33 辅助变量是存在的.. Yangff 20:30:42 换来干嘛。 Yangff 20:30:44 额= =？ wyl8899 20:30:43 在你的脑海当中 Yangff 20:31:00 但是他没有存辅助变量的系数啊。。 wyl8899 20:31:20 一开始 x[l+n]=a[l][0]+∑a[i][j]*x[j]>=0对吧 Yangff 20:31:34 嗯…… wyl8899 20:31:32 系数根本就是1嘛.. 干嘛要存下来 Yangff 20:31:49 换了就不一定是1了啊。。 wyl8899 20:31:44 然后来看看那个x[e] wyl8899 20:32:12 由于pivot的条件，已经保证了A[l][e]>0 wyl8899 20:32:20 换句话说a[l][e]=-1 Yangff 20:32:38 = =? wyl8899 20:32:41 （假定只有1/0/-1的情况 Yangff 20:33:02 a[l][e]>0所以a[l][e]=-1？ wyl8899 20:33:13 A[l][e]>0 , a[l][e]<0 , a[l][e]=-1 Yangff 20:33:27 哦哦 wyl8899 20:33:26 于是我们移一下项.. wyl8899 20:33:51 x[l+n]=a[l][0]+∑(j!=e)a[i][j]*x[j]+a[l][e]*x[e] wyl8899 20:34:19 x[e]=a[l][0]+∑(j!=e)a[i][j]*x[j]+(-1)x[l+n]>=0 Yangff 20:35:36 嗯。。 wyl8899 20:35:33 给x[l+n]起个新的名字，叫做x[e] 给x[e]起个新的名字，叫做x[l+n] wyl8899 20:36:02 x[l+n]=a[l][0]+∑a[i][j]*x[j] , 只要a[l][e]=-1就完成任务了 Yangff 20:36:58 等等…… Yangff 20:37:09 难道不要把原来的x[l+n]移过去吗？ Yangff 20:37:16 移到右边 wyl8899 20:37:16 移了啊 wyl8899 20:37:37 很显眼的(-1)x[l+n] Yangff 20:38:00 a[l][e]=-1只是把x[e]移到左边啊。。 Yangff 20:38:14 左边的l（l+n）不应该移到右边吗？ wyl8899 20:38:25 a[l][e]=-1是在把x[l+n]移到右边去啊 Yangff 20:38:49 0 0？ wyl8899 20:38:42 x[e]成为基本变量了以后系数永远是1 不存 Yangff 20:39:00 对。 wyl8899 20:39:06 所以这里我们设定的是x[l+n]在x[e]的等式里的系数 wyl8899 20:39:31 但是由于他们已经调换名字了.. 所以是a[l][e]=-1 Yangff 20:39:45 等等……也就是说a[l]存的是原来的a[e]经过改变后的系数？ Yangff 20:40:05 a[e]存的是移项后的a[l]？ wyl8899 20:40:04 对对对对 Yangff 20:40:16 哦！ wyl8899 20:40:17 有没有觉得很碉堡 wyl8899 20:40:31 所以从头到尾都只有m个(不)等式 Yangff 20:40:47 也就是说，永远保证下标是等式左边的下标？ Yangff 20:40:55 果然碉堡。。 wyl8899 20:40:57 但是.. 输出方案就要麻烦一些了 Yangff 20:41:12 = =。。 Yangff 20:41:31 等等…… Yangff 20:41:35 这样好像还是有点问题。。 wyl8899 20:41:57 呃.. 哪里有问题？ Yangff 20:42:43 如果只保存了n（也就是原始约束个数）个不等式的话，去哪里和新增加的辅助变量交换。。 Yangff 20:43:05 既然下标一定是等式左边的下标 wyl8899 20:43:59 辅助变量.. 你是说n+1..n+m这些吗 Yangff 20:44:12 嗯。 Yangff 20:44:18 因为是要和他们交换啊。 wyl8899 20:44:19 他们从头到尾都只存在于你的脑海里 Yangff 20:44:33 ^ Yangff 20:44:44 那怎么枚举。。 wyl8899 20:45:04 你是说在确定PIVOT的对象的环节？ Yangff 20:45:16 毕竟他们也可能被选中啊。。 wyl8899 20:45:16 被选中？ Yangff 20:45:37 就是说，下标为n+1,...n+m的变量。 Yangff 20:45:52 也可能变成非基变量啊。。 Yangff 20:46:32 如果不存他们的话，你的下标只能在0~n之间变。。 wyl8899 20:46:35 所以说是下标永久对换啊 wyl8899 20:46:38 这么说吧.. 继续前面的PIVOT(l,e) wyl8899 20:46:52 a[e][]存了移项以后的a[l][] wyl8899 20:46:58 不对.. Yangff 20:47:10 我知道下标是永久对换的。但是你换的范围只有0~n Yangff 20:47:16 1~n Yangff 20:47:28 那不就没有意义了，我本来就是这n个不等式的。。 wyl8899 20:47:24 我不懂应该怎么解释清楚.. wyl8899 20:47:30 不管你怎么PIVOT Yangff 20:47:41 ><.. wyl8899 20:47:36 永远只有n个不等式 Yangff 20:47:59 好吧。。 Yangff 20:48:01 换句话说。 Yangff 20:48:56 一个x[n+2]（基）和x[2]（非基）在PIVOT之后的下标分别是什么（其中n+2是不占在a数组下标的） wyl8899 20:49:53 x[2]永久的... 消失了 x[n+2]取而代之 Yangff 20:50:51 也就是说……系数是有n+2的位置的？ Yangff 20:51:00 只是不等式没有？ wyl8899 20:51:39 不是啊... wyl8899 20:51:46 x[2]不是已经消失了吗.. Yangff 20:52:03 嗯。。 wyl8899 20:52:05 所以现在x[n+2]完全的成为了x[2] Yangff 20:52:16 哦！ Yangff 20:53:35 我是说在系数中。。 wyl8899 20:54:00 呃... 在这次PIVOT之后 一切a[][2]都指的是x[2] 也就是原来的x[n+2] Yangff 20:54:16 x[l]=a[l][0]+∑a[i][j]（这里有没有n+2的位置）*x[j] Yangff 20:54:19 哦。。 wyl8899 20:54:30 在PIVOT的后半部分已经完整的完成了这个取而代之的工作 Yangff 20:54:47 我知道了。。 wyl8899 20:56:03 可以写一份《论如何读懂一类单纯形代码》来造福人类了... Yangff 20:56:58 那怎么知道a[i][..]带边的左边的x的下标……难道也直接换成x[i]？ Yangff 20:57:28 把x[n+2]直接取代x[2]的一切位置，名字，下标？ wyl8899 20:58:17 恩 Yangff 20:58:30 *以及在别的不等式中的x[2]也换成x[n+2]？ Yangff 20:58:32 好啊并。。 Yangff 20:58:34 好吧。。 Yangff 20:58:35 我懂了。。 Yangff 21:00:00 那么…… 这一行的循环范围并没有超过不等式的数量…… Yangff 21:00:13 他是怎么把辅助的不等式考虑进来的…… Yangff 21:00:23 还是说这个m=n+m？ wyl8899 21:01:11 这一行是在选择一个在目标函数中系数为负的非基本变量吧 Yangff 21:01:37 嗯。。 wyl8899 21:01:48 那关基本变量(你愿意叫他辅助变量也可以)什么事.. Yangff 21:02:01 说错了= = Yangff 21:02:03 下面那个= = Yangff 21:02:12 他只循环到n啊。。 wyl8899 21:02:12 因为只有n个不等式对吧.. Yangff 21:02:24 嗯。。。 wyl8899 21:02:26 那就没事了啊.. 这不是考虑清楚了么 Yangff 21:02:43 = =。。 Yangff 21:02:48 总共有n+m个不等式啊。。 Yangff 21:02:55 只是当前有效的n个。。 Yangff 21:03:01 别的都被这n个确定了啊。。 Yangff 21:03:16 但是交换的时候不是应该从m这里拿吗。。 Yangff 21:03:22 （好吧，我n，m都快乱了） wyl8899 21:03:29 那就明确一下吧 n是约束个数 m是变量个数 Yangff 21:03:41 嗯。。 wyl8899 21:03:39 *非基本变量个数 Yangff 21:03:55 嗯。。 wyl8899 21:03:58 那n+m个不等式... Yangff 21:04:10 嗯。。 Yangff 21:04:15 *-* wyl8899 21:04:08 有n个已经被存下来了 Yangff 21:04:21 嗯 wyl8899 21:04:23 其余的m个都是非负性限制不是吗.. Yangff 21:04:40 嗯 wyl8899 21:04:38 所以还有什么问题呢.. wyl8899 21:04:59 不管这个PIVOT怎么乱来 松弛型的形态都没有改变 Yangff 21:06:41 但是…… Yangff 21:06:48 他这里怎么看都是在自己和自己松弛啊。。 Yangff 21:06:52 pivot wyl8899 21:07:55 啊.. Yangff 21:08:46 l∈[1,n] e∈[1,m] 如果我要和n+m松弛怎么办。。 Yangff 21:08:48 pivot Yangff 21:09:11 这里l永远不可能是n+m啊。 Yangff 21:09:25 但是真正操作的时候是有可能用到的啊。。 wyl8899 21:09:35 你是说l的取值范围啊 Yangff 21:09:48 嗯！ Yangff 21:10:05 毕竟l决定了e将来的下标 wyl8899 21:09:59 l是1..n就取遍了n个非基本变量啊 wyl8899 21:10:10 不对.. wyl8899 21:10:14 n个基本变量 Yangff 21:10:36 但是pivot里面不管是不是非基变量，都是直接a[l]直接取了啊。。 Yangff 21:10:58 但是a[l]显然是非基本变量啊 Yangff 21:11:09 a[l+n](不存在)才是基本变量吧。 wyl8899 21:11:30 但是a[l][]保存的是(x[l+n]=)a[l][]+∑a[l][j]*x[j]不是么 Yangff 21:11:44 ！！ Yangff 21:11:47 懂了！ Yangff 21:11:59 太感谢了……*_* Yangff 21:12:19 （这写法大坑啊…… wyl8899 21:13:03 所以我说应该可以写一份《论如何读懂一类单纯形代码》来造福人类了... Yangff 21:13:26 同意。。 Yangff 21:15:51 稍等……如果这样的话…… a[l][e] = -1;后面不应该跟一个 a[l][l] = 1;吗？ wyl8899 21:16:16 a[l][l]存的是啥？ Yangff 21:16:28 哦哦哦。。 Yangff 21:16:31 我看错了= = Yangff 21:19:18 /** e成为基变量，位置为n+l n+l成为非基变量，位置为e **/ inline pivot(int l,int e) Yangff 21:19:26 所以这是这个函数的意思么。。 wyl8899 21:19:32 恩... Yangff 21:19:46 大坑/A\ wyl8899 21:19:47 绝对的大坑...
uva10489
usaco ditch
评论 (0)
