沙渺很忙

残留网络：一个不可忽视的小问题

沙渺 — Sun, 06 Jul 2008 14:33:08 +0800

残留量=容量-流量，只需要这样吗？

提问：对如图所示的残留网络R，沿标注的路径增广后，得到的残留网络是R*吗？

R(u,v) = C(u,v) - F(u,v)，看起来这样是没问题。但这样做可能造成潜在的错误。

例如一个网络流求二分图最大匹配的例子，假设使用时间O(ef*)的Ford-Fulkerson朴素算法。

在这个例子里，我们看到最大流显然是2，但如果残余网络只是容量减流量，可能求不到最大流。

放弃回溯：危险的逻辑！

只从正确性而言，显然在选择增广路径的时候可以任选，但我们不清楚某一条路径的增广，是否会影响其它的路径。例如上图，可以由"左1-右1"增广也可以由"左1-右2"。但是经由"左1-右1"的增广，就会切断"左2-右1"的增广路径而得不到最优解。

思考一个逻辑的问题：不能回溯的搜索算法是什么？——显然，搜索失去回溯，就会变成随机化或者错误的贪心。回到网络流问题，正因为增广路径之间会互相影响，所以应用增广路径解决网络流问题，需要“回溯”的逻辑来纠正错误。

正确的方法

纠正这个错误的方法很简单，就是在对路径进行增广时，不仅要减去增广流量，同时一定要加上与流量相反的逆弧。

还是上面的二分图的问题，以下是正确的方法：

那么，本文开头的残留网络R增广后，正确的结果是什么呢？

在2008年吉林省计算机奥赛省选赛中，碰到一个二分匹配，我正好犯这个错误，直接将Dinic写成随机化，被狂减80%的分数。谨记教训。

原创文章，作者：沙渺
本文链接：残留网络：一个不可忽视的小问题

作者沙渺版权所有。
网络转载本文，必须注明出自“沙渺很忙”博客并以链接形式注明出处。
纸质媒体刊载本文，必须事先征得作者同意。
内容发布行为尊重《知识共享署名-相同方式共享 2.5 中国大陆许可协议》的规定。
作者无法对使用本文所产生的后果负责，以本文指导实际工作请慎重。
以上规定适用于本文，对于本站其他内容不可援引。

2008计算机奥赛吉林省选：总结

沙渺 — Wed, 18 Jun 2008 19:02:09 +0800

今年省选赛的题又难又偏，高级算法考了很多，但基础知识一点都没照顾到。
没导向没立场，不由得让人怀疑有多少“奥步”在里面。还好这不是创新大赛，分数永远是最硬的。

自己拜测试数据所赐，多少也靠点运气，算是涉险出线。省选赛写完总结到此为止，国家赛再努力。
分数242, 名次3, kviz100, codes10, checkmate20, knight32, master80.

下载

jloi08-prob-data-sol.zip
题目、数据、官方解题报告、清橙评测包，但没有标程。全部选手的source欠奉，免得伤人。

纳米盘：点击进入下载页面
box.net：点击进入下载页面
Windows Live Skydrive：点击直接下载

各题总结

A 提示问题 (kviz)

没有要点。注意除3时四舍五入，还有“吭哧塞”和“吭哧喂”代码时仔细检查，不要出错。

B CODES (codes)

(广搜尝试中)

转载的题。解题报告很详细。

C 将军 (checkmate)

问题实质整理一下，实际上就是每条正斜线(／)上最多有1个象，每条反斜线(＼)上最多有1个象，但有一些格子不能用（与预设的棋子冲突）。

每个点占有1条正斜线，一条反斜线。而每条斜线上只能放一个象。当然看起来像n皇后，但不是搜的。

构二分图，一侧是正斜线的编号，另一侧是反斜线的。每一个可以放象的点视为一条边。做二分最大匹配。

帖一幅图帮助理解。红、蓝色是两种对角线的编号，打勾的格可以放象。
下面是构出的二分图

算法可以网络流，也可Hungary算法。但是我写的Hungary总是第10个测试点超上那么零点一几秒。

放“象”和放“车”在本质上是一样的，都用二分匹配做。只有放皇后必须搜。

记得当年和FancyMouse讨论过此题，被大牛告知是最大二分匹配。比赛一看，知道怎么做，开心^_^。
可是赛前准备的网络流有错误，结果本来自鸣得意的题T_T了，应该a掉的题被灭了80。

D 可怜的骑士 (knight)

竟然出现了NP类问题。无话可说。
正确算法是hamilton环的近似算法。不常用，也不想分析，可参见算法导论。

比赛时随机化加卡时跑的-_-b|||。
话说评测机的时限是6秒，结果按1秒估计的，怕出问题还特地卡了0.75秒，亏死了。
这样骗了32分，竟然还是全场最高。我想大概是没有人钻研过近似算法的问题。

E 棋局定式 (master)

啰哩罗嗦了半天，实质就是在原字符串中查找子字符串（只需回答是否存在）。KMP算法理想。

本题用朴素算法也有70分。
我在程序里使了两个小手段：用位运算把每个操作压缩成short int，并使用memcmp()直接比较内存。
结果很神气的多骗10分，并且通过的点也比直接来少花了大约2/3时间。
比赛策略上这样做是很划算的，因为写KMP多得20分，不如花时间写CODES或checkmate。

原创文章，作者：沙渺
本文链接：2008计算机奥赛吉林省选：总结

作者沙渺版权所有。
网络转载本文，必须注明出自“沙渺很忙”博客并以链接形式注明出处。
纸质媒体刊载本文，必须事先征得作者同意。
内容发布行为尊重《知识共享署名-相同方式共享 2.5 中国大陆许可协议》的规定。
作者无法对使用本文所产生的后果负责，以本文指导实际工作请慎重。

第2届吉林省大学生程序设计竞赛：观摩总结

沙渺 — Tue, 10 Jun 2008 14:35:20 +0800

第二次参加省赛，高中身份，自然还是没奖的Guest。
这次比我还强些的coder夏yh(因故)没来，只有自己一个人编码。就像DD所说的，一个人编码的确是很辛苦的事情。最后一小时本来可以试试H题，但我实在是干不动了。
由于夏yh的缺席，我还请了同班的MO强人（但不懂计算机竞赛）鲁z，希望能帮忙做数论和计数问题。但最后让他失望了：数论没有，计数问题也是（和数学关系不大的）搜索剪枝。

最后做出了5道题(ABCDI)，369分钟，全场第9名。
虽然成绩还可以，但AC的几道题毕竟比较水，以这样的水平参加再高级别的比赛会很惨。
自己唯一满意的就是理想的时间：2个小时刷完5道题，罚时总共也只有2次。
和另一支高中的Guest(东北师大附中)相比，很遗憾，输了附中5名。
明年再来吧。

照片三张：

从左至右：杨xq(我的队友)、沙渺、李px、李px的队友
和东北师大附中的合影。东北师大附中是另一支高中的强队，全场第4。

从左至右：吴h，王rt，沙渺，李dc，杨xq
我们学校1队和2队的合影
1队队员：沙渺(coder)、鲁z(数学，照相缺席)、杨xq。9名，5题369分钟。
2队队员：吴h(coder)、王rt、李dc。53名，2题137分钟。

官方网站上我们队唯一一张照片。鲁z在这张照片里。
距离镜头从远到近：杨xq、沙渺、鲁z

题目下载

jlcpc08-problems.zip

纳米盘：点击打开下载页面
box.net：点击打开下载页面
Windows Live Skydrive：点击直接下载

测试数据欠奉，请移步吉大online judge进行练习。

在线练习

吉林大学online judge

比赛成绩

jlcpc08-standings.xls

纳米盘：点击打开下载页面
box.net：点击打开下载页面
Windows Live Skydrive：点击直接下载

吉大官方：http://acm.jlu.edu.cn/joj/standing_new.php?cid=103

前20名：

各题总结

A Welcome 2008

不做分析。有这样的水题，还有队伍打0分，我在想这是不是过于丢脸。

B Stock Wave

动态规划，思想和最长XX子序列类似。

题目不难，但全场通过率只有6%，究其原因在于题目中有陷阱。题目的原意是找最长的“波”，但题目要求奇数点(odd)在下(less)，偶数点(even)在上(greater)。也就是说“波”一开始必须是上升的“/\”型，而不是下降的“\/”型。
因为这个自己当时也交了2遍——交第2遍的时候就知道这个会坑不少人。比完赛一看，提交321全对21（6.54%），果不其然。

C Central Avenue Road

线性规划。

这次的几何题出乎意料的简单：

整数问题 - 无误差
解析几何即可解决 - 不必动用计算几何
数据规模小 - 只需枚举

只能说这样的便宜真是不可多得。

D Function Value

模拟。

比赛当时的素数判定用了打表+试除。托测试数据的福，没有用miller-rabin。
鲁z说n是素数时有f(n)=floor(log2(n))，但裁判机的WA证明这个不对。但我想n是素数时是不是有一种非递归的办法呢？

E Billboard

二分构图，在相同的字母之间加边，容量1，费用等于移动距离。然后最小费用最大流。

比赛当时用的贪心，就是说先选不动的，再选动1格的，再选2格的以此类推。但这么做始终WA，可能某些卡片稍微多动两格，会得到更少的总步数？但我还没找到具体的反例。
注意，这句话是裁判说的：空格也算一张卡片。

F Civilization Map

广度优先搜索。

没难度，但非常的罗嗦。比赛当时也只有第一名（全对）的队伍完全正确。
“要有人能够对付麻烦的题，并保证一定的通过率，大多数的比赛都至少有一道这样的题。”今天才明白这句话是多么的经典，谁说的来着。

G What is your level

抱歉，解法欠奉。

直接算法看到题的同时也想出来了，但200000的规模显然需要nlogn的数据结构加速。现在还没想出来。

H Lamp Matrix

搜索剪枝。暂时没有找到什么有效的特殊性质，3^20的复杂度枚举刚好超时，搜索剪枝只能说可行。
本来最后一小时可以攻这道题，但我实在干不动了-_-b。正是DD所说的体力问题。

I Digit Game

高精度。放在这个位置纯粹是唬人。我在想出个几十万位考考排序还能有点意思。
裁判说的：升序排序时，允许前导0。题目中“不要前导0”只是指最后输出时。

============================================================

链接一个第6名（吉林大学new task队）的小总结：
http://hi.baidu.com/fandywang_jlu/blog/item/b542abef09642eeace1b3e9f.html

第4名（北华大学启航队，牛）的blog：
http://www.bhjsj.cn/aowarmen/?p=8

原创文章，作者：沙渺
本文链接：第2届吉林省大学生程序设计竞赛：观摩总结

作者沙渺版权所有。
网络转载本文，必须注明出自“沙渺很忙”博客并以链接形式注明出处。
纸质媒体刊载本文，必须事先征得作者同意。
内容发布行为尊重《知识共享署名-相同方式共享 2.5 中国大陆许可协议》的规定。
作者无法对使用本文所产生的后果负责，以本文指导实际工作请慎重。

在线绘图网站推荐

沙渺 — Tue, 27 May 2008 16:54:06 +0800

2008.5.28：大好消息，Best4C从当机中恢复。补充上介绍。
先说明一点，这里的“绘图”指的是图论的图形、组织结构图、网络示意图等等，而不是艺术的绘画，不要误会。

最早知道在线绘图是在CSDN上看到“用best4c画出文章中的图形”。最近写Treap的文章需要画一些二叉树的图，想到了用在线绘图工具。可是碰巧Best4C挂了。用百度（也就意味着在国内）查询了一下一无所获。用google找到几个外国的网站，在这里推荐给大家。

Best4C
http://www.best4c.com
唯一一个国内的工具

不硬性限制存储。素材丰富，丰富到竟然可以画化学仪器一类的东西。并且直接支持外链。可导出PDF(矢量格式)、PNG和JPG。
这是联想实验室(lenovolabs)的作品，的确处处体现了大公司的风范，值得使用。
但是有许多地方在细节上处理不好，操作不是非常的舒服，例如：没有snap grid，同时调整大小时竟然不能用shift或alt固定比例。我在想忽视细节是不是国内公司的通病。

随手画了一幅Dijkstra，这是外链的演示：

小图：http://www.best4c.com/Best4cUserFiles/20080529/190881_1212046634182_small.jpg
点击看大图：http://www.best4c.com/Best4cUserFiles/20080529/190881_1212046634182.png

接下来就全是国外的了。基本上都基于Flash，在线翻译不好用。请确信对自己的英语有信心。

DrawAnywhere
http://www.drawanywhere.com

必须注册，支持jpg png gif输出但有广告。可以在线存放3张图，太吝啬了。
功能比较简单。问题很多：
第一，没有snap grid吸紧网格，不好准确对齐；
第二，连接线的两端竟然无法贴紧图形，导致移动图形的时候连接线不能跟着跑。这一点对于图论作图非常不利——因为作图时图中的点有时会挪动，这时手动更新边是很麻烦的。
第三，我在IE6和Firefox中竟然都无法框选多个图形，按shift或ctrl也不能多选，匪夷所思的大bug。

Gliffy
http://www.gliffy.com

这个的功能可以说是大哥大了，图形资源丰富，并且应有的功能很全面，比如snap grid，连接线吸合（见图），导出图像等等。
但也不是说没有问题：
也必须注册。
存储空间仍然非常吝啬，5张而已；并且在线存储有bug，存盘的文件点不开。
导出的图象中汉字变得很难看。
最郁闷的是一条广告占去了画布上边的一小条，编辑小图象时很不爽。

Autodesk Labs - Project DRAW
http://draw.labs.autodesk.com

来头不小，这可是AutoCAD公司实验室的作品。
不必注册——这一点很有特点。同时，注册之后存放的文件数量也没有限制，比前面两个大方多了。
图形资源和Gliffy一样丰富。功能也全。
但是问题还是有：中文支持不好，导出的图象中不支持汉字，会全部变成方块，太让人失望了。

这些资源尤其适合blog writers，或者杂志、论文的撰稿人。希望能有所帮助。

原创文章，作者：沙渺
本文链接：在线绘图网站推荐

作者沙渺版权所有。
网络转载本文，必须注明出自“沙渺很忙”博客并以链接形式注明出处。
纸质媒体刊载本文，必须事先征得作者同意。
内容发布行为尊重《知识共享署名-相同方式共享 2.5 中国大陆许可协议》的规定。
作者无法对使用本文所产生的后果负责，以本文指导实际工作请慎重。

二叉平衡查找树：Treap

沙渺 — Mon, 26 May 2008 23:50:35 +0800

示例程序下载，没有对象封装，只说明原理。比赛使ok，做软件慎用。

treap-demo.cpp

纳米盘：点击打开下载页面
box.net：点击打开下载页面
Windows Live Skydrive：点击直接下载

TREAP首先是TREE（二叉查找树），其次具备HEAP（堆）的特性。在查找树保持基本性质不变的同时，TREAP的每一个结点随机设置一个权值prior，权值满足堆的性质。

TREAP同时满足这两个性质的方法是：首先满足查找树性质，再通过左旋或右旋变换，不破坏查找树性质的同时，再满足堆的性质。

左旋/右旋的目的在于操作某个父结点和它的一个子结点——子结点上去，父结点下来。以左旋为例：

可以看到，在左旋之后，P,R,a,b,t互相的大小关系没有变化。例如，a始终在P的左子树上。

右旋也一样：

通过左旋和右旋，结点可以在查找树中自由上下移动。——结点的上下移动很容易和堆结点的上调和下调对应。

左旋与右旋编码也需要细心注意几个问题：

针对子结点R或者父结点P都可以。
注意大前提，必须要有一父一子两个结点，也就是说，不能把根结点通过旋转向上调——再向上去哪？
尤其要注意有些子树（上图a,b,t,x）可能是不存在的，先!=NULL再访问。
如果存储了父指针，子结点指向新的父亲之后，父亲必须立刻收编（指向）这个子结点。两者必须配对进行，否则树上的父子关系容易一团糟。

下面的这个程序是针对子结点写的。只有左旋，希望右旋你能自己完成。

假定存在如下定义的node：
struct node
{
node *left, *right, *parent;
int key, prior;
};
*/
void leftrot(node *r)
{
if (r->parent == NULL) return;
else
{
node *p = r->parent;
node *t = r->left;
//r继承p的父节点关系
r->parent = p->parent;
if (p->parent != NULL)
{
if (p->parent->left == p)
p->parent->left = r;
else
p->parent->right = r;
}
//p归入r的右子树
r->left = p; p->parent = r;
//t结点到位
p->right = t; if (t != NULL) t->parent = p;
}
}

插入操作的前半部分是大路货，和一般二叉查找树相同。

node *ins(int _key, node *root) //返回新的根

{
node *pos = root, *prev = NULL;
while (pos != NULL)
{
prev = pos;
if (_key < pos->key)
pos = pos->left;
else if (_key > pos->key)
pos = pos->right;
else
{
/* 此处应该更新结点内容，
因为查找树中不应该有关键字相同的结点。
这个范例程序中，结点没有内容只有关键字，
实际应用中请酌情增加。 */
return root;
}
}
//newnode增加到一个叶子结点的位置
node *newnode = new node;
newnode->key = _key;
newnode->left = newnode->right = newnode->parent = NULL;
if (prev != NULL)
{
newnode->parent = prev;
if (_key < prev->key)
prev->left = newnode;
else
prev->right = newnode;
}
else return newnode; //在此之前树是空的，newnode成为新的根

后半部分TREAP专有，通过旋转，使新结点从叶子开始不断上调，直到满足堆性质。

//TREAP: 调整树满足堆性质

newnode->prior = rnd();
while (1)
{
if (newnode->parent == NULL) return newnode; //此时newnode到达根的位置
else
{
if (newnode->prior <= newnode->parent->prior) //已经符合堆性质
break;
else
{
if (newnode == newnode->parent->left) //newnode在左子树 - 右旋
rightrot(newnode);
else
leftrot(newnode); //newnode在右子树 - 左旋
}
}
}
return root;
}

查询与一般的二叉查找树毫无差别。

node *query(int key)

{
node *pos = root;
while (pos != NULL)
{
if (key == pos->key)
break;
else
if (key < pos->key)
pos = pos->left;
else
pos = pos->right;
}
return pos;
}

TREAP中删除也不难，只需要将需要删除的结点转到叶结点上直接扔掉。我觉得比找前驱再分类讨论方便多了（假如愿意，一般的二叉查找树也能这么做。）

void delnode(node *pos)

{
//pos转到叶子
while((pos->left)!=NULL || (pos->right)!=NULL)
{
if (pos->left == NULL) leftrot(pos->right); //只有右子树，右子结点左旋
else if (pos->right == NULL) rightrot(pos->left); //只有左子树，左子结点右旋
else //左右子树均有，权较大的向上（假设是大顶堆。小顶堆就是较小的）
if ((pos->left->prior) > (pos->right->prior)) rightrot(pos->left);
else leftrot(pos->right);
}
//去除与父结点的联系
if (pos->parent != NULL)
if (pos->parent->left == pos) pos->parent->left = NULL;
else pos->parent->right = NULL;
pos->parent = NULL;
//释放内存
delete pos;
return;
}

无论输入如何，TREAP的期望时间复杂度总是O(nlogn)。因为TREAP中，堆分担了调节平衡的责任，也就是说左右子树的平衡不再依赖于输入的顺序，而是取决于为结点分配的权值。权值是随机的，在n很大时（几千就够）服从统计规律，所以我们总是可以期望O(nlogn)的时间复杂度。 TREAP比AVL, splay都好写的多，相比红黑树更是容易的多。很多情况下非常实用——当然，这个“实用”更多的意味着顺手。TREAP不用硬背——只要记住先写Tree再加Heap这个顺序，coding的确是信手拈来，轻松愉快。

原创文章，作者：沙渺
本文链接：二叉平衡查找树：Treap

作者沙渺版权所有。
网络转载本文，必须注明出自“沙渺很忙”博客并以链接形式注明出处。
纸质媒体刊载本文，必须事先征得作者同意。
内容发布行为尊重《知识共享署名-相同方式共享 2.5 中国大陆许可协议》的规定。
作者无法对使用本文所产生的后果负责，以本文指导实际工作请慎重。