Thunder is thunderstruck.................................

个人资料Thunder is thunderstruck...照片日志列表

工具

帮助

日志

2月11日

Network Flow & Related Problems

网络流和相关问题
问题预备
最短路

问题
    给出：一个有向连通带权图，包含源点和汇点。

    每一条弧的权表示那条弧的容量。一个图的流通过分配整数量给每条边来达到：
      ·通过每条弧的流不大于这条弧的容量
      ·除了源点和汇点的每个点，流入量等于流出量

    取源点的流出总量减去流入总量（或汇点的流入总量减去流出总量的最大值

例
    给出：水管的设计和每条水管的容量。水管里的水必须从上往下流，所以每条水管里，水只能向一个方向流。

    计算能从头（自来水厂）流到尾（您的农场）的水量。

算法：
    算法（贪心）通过迭代增加从源到汇的流来建立网络流。

    从每条弧的权等于初始的权开始（弧的权符合那条弧里还未使用的容量）。//-_-#

    给出当前的图，找到从源到汇的一条路径，这条路径上的弧都是非0权。计算这条路径的最大流，叫它路径容量。//传说中的增广路径... 路径容量 = 瓶颈容量

    对于每一条路径上的弧，给弧的权减去路径容量。另外，给路径中的反向弧（在相同两点之间的弧，不过方向相反）加上等于和路径容量相等的权（只要反向弧存在，就增加它的权）//调整增广路径

    继续调整路径直到没有增广路径存在。

    这能保证停止，因为您加上每次至少一单位流（权总是整数），并且流严格单调递增。增加反向弧的权相当于减少路径上的流量。

    如果您对算法的细节分析感兴趣，请教Sedgewick.//谁啊..-_-....

    这是算法的伪代码：
    1   IF (源点 = 汇点)
    2       总流 = 无限大
    3       DONE

4 总流 = 0

    5   WHIEL (TRUE)
    6 # 找到从源到汇的最大的容量的路径
    7 # 用修改过的Dijkstra算法 //在Chapter 4 的ditches就要用Bellman-Ford了..
    8     FOR 所有的顶点 i
    9       prevnode(i) = nil
    10      flow(i) = 0
    11      visited(i) = FALSE
    12    flow(源点) = 无限大

    13    WHILE (TRUE)
    14      最大流 = 0
    15      最大流节点 = nil
    16      # 找到最大容量的未访问节点
    17      FOR 每个顶点i
    18        IF (flow(i) > MaxFlow AND NOT visited(i))
    19          MaxFlow = flow(i)
    20          MaxLoc = i
    21        IF (MaxLoc = Nil)
    22          退出循环
    23        IF (MaxLoc = 汇点)
    24          退出循环
    24a       visited(MaxLoc) = TRUE
    25        # 调整相邻节点
    26        FOR MaxLoc的所有相邻节点 i
    27          IF (flow(i) < min(MaxFlow, MaxLoc到i的容量))
    28            prevnode(i) = MaxLoc
    29            flow(i) = min(MaxFlow, MaxLoc到i的容量))
    30    IF (MaxLoc = Nil)    # 没有路径
    31      退出循环

32 路径容量 = flow(汇点)
33 总流 = 总流 + 路径容量

      # 把那个流加到网络里适当调整容量
    35    当前节点 = 汇点
            # 对于增广路径上每条弧, prevnode(当前节点), 当前节点
    36    WHILE (当前节点不为源点)
    38      下一个节点 = Prevnode(当前节点)
    39      下一个节点到当前节点的容量减去路径容量
    40      当前节点到下一个节点的容量加上路径容量
    41      当前节点 = 下个节点

这个方法的运行时间为O(FM)，F是最大流 M是弧的数目. 运行时间通常更短, 因为算法每次总是尽可能大的提升流。

为了确定每条弧上的流，比较开始的容量和最后的容量。如果最后的容量变少了，区别就在于通过这条弧的流。

当有回路的时候，这个算法可能产生死循环。

实例
    考虑下面那个网络，源点为5，汇点为2
    Graph1
    最大增广路径为(5,1,3,6,2)
    Graph2
    瓶颈弧是1->3，容量为5。因此，把路径上所有的弧减去5，把反向弧上加上5（如果需要，添加弧）。这就是得到的图：
    Graph3
    在新的图里，最大增广路径为(5,4,6,2)
    Graph4
    瓶颈容量为3，再来一次。
    Graph5
    现在网络的最大容量路径为(5,4,6,3,2)
    Graph6
    瓶颈为1，再来一次
    Graph7
    结果图从源到汇就没有增广路径了。唯一可以到达的源点的就是它自己和1号节点
    Graph8
    算法加了三次流，第一次是5，第二次是3，最后一次是1。因此，最大流是9。

扩展
网络流问题是很广泛的，通常和图结合在一起。

扩展到无向图，只需要简单的把无限边扩展为两条相反方向的弧就可以了。

如果您想要限制任意一个节点的通过量，把一个节点拆成两个，一个流入节点，一个流出节点，把流入的弧连到流入节点里，流出弧连到流出节点里，在流入节点和流出节点之间加上一条弧，容量为限制。

如果您有多源点汇点，建立一个虚拟的源点和虚拟的汇点，虚拟的源点射出弧到每个源点，汇点射出弧到虚拟汇点。容量无限。

如果您有实数型的权，这个问题不再保证能出解，尽管答案能逐渐逼近。

可选问题
网络流能用来解决其他的一些不明显的问题。

最大匹配
给出两个对象集合（叫他们A和B），你想要把A和B中的元素尽可能多的匹配起来，约束条件是只可以两两配对。这就是最大匹配问题。

      把这个问题用网络流的形式表现出来，建立一个源点，射出容量为1的弧给A的元素，建立一个汇点，B中的元素射出容量为1的弧。另外，如果A中某个元素可以和B中某个元素匹配，从A的这个元素向B的那个元素射出一条容量为1的弧。用网络流算法确定哪些A元素到B元素的弧被用到。

    最小割
      给出一个带权无向图，最小割就是一个权和最小的，能够把两个给出点分开的边的集合。

最小的权和就是两个节点之间的流。

要确定路径，按照权递增的顺序尝试删除每条边，看它是否减少了网络流，减少量为边的容量。第一个这样的边就是最小割的元素，去掉这条边继续在图上操作。

用相同的技巧，把节点用容量限制，这能够扩展到求节点的割。有向图也是一样。然而，它不能够解决所谓的“最佳匹配”问题，每一对都有一个“佳值”，而且您想要得到最高“佳值”和的匹配。

例题
    如果问题讨论取流或者其他从一个地方到另一个地方东西的移动的最优值，就可以几乎确定是最大流。如果它讨论的任何一类东西的最大配对，就可能是最大匹配。

    病毒流
      您有一个通过网线连接的计算机网络。数据可能从任何一个方向流经网线。不幸的是，一台网络里的机器染上病毒，您需要从中心服务器隔离这台机器来防止病毒传染。给出关闭一对机器连接的代价，计算控制病毒传染到服务器的最小的代价。

      这就是最小割问题。

    伐木工人的计划
      不同种类的树需要雇佣拥有不同的技巧的伐木工人来正确的砍树。不管哪种树或伐木工人，砍一棵树需要30分钟。给出伐木工人的信息，和哪种树需要哪位才能正确的砍倒，以及数的信息，计算在半小时内砍倒的最多的树的数目。

牛的电话联系（USACO 锦标赛 1996）
给出原野里的一组电脑，和电脑之间连着的网线，要想阻止给定两台电脑的联系最少需要关掉多少网络中的电脑。假定两台给出的电脑没有关掉。

这相当于最少节点割的问题。两台给出的电脑标上源点和汇点。电缆是双向的。把每个点拆成流入点和流出点，这样我们就能够用1限制任何一台电脑。现在，网络里的最大流就相当于节点最小割了。

      为了具体确定割，反复删除节点，直到您找到一个能降低网络流量的节点。

    科学展览审定
      一个科学展览由N个学科，和M个裁判。每个裁判愿意审定某些学科，每个学科需要一些裁判。每个裁判只能够审定在给出的科学展览中的一个学科。您在这些条件下总共能分配给多少裁判任务？

      这是一个很类似最大匹配的问题，除了每个学科需要可能多于一个裁判。解决这个问题的最简单的方法是把从科目到汇点的弧的容量赋予需要裁判数的值。

    石油管道设计
      给出阿拉斯加管道线的设计（每条管道的容量，和管道如何连接），以及每个交点的位置，您想提高朱诺和费尔班柯斯之间最大流量，但您的钱只够添加一条容量为X的管道。此外，管道只能10英里长。这条管道添加在哪两个交点能最大程度的提高流量？

要解决这个问题，对于距离10英里以内的每一对交点，添加一条管道，再计算从朱诺到费尔班柯斯的流量增加值。每一个子问题都是最大流。

17:35 | 添加评论 | 阅读评论 (1) | 固定链接 | 写入日志

2月1日

USACO Chapter4

Chapter 4
4.1 nuggets Beef McNuggets
  用简单的递推, 顶多开800000000的Boolean数组
  递推公式 opt[i + size[j]] = true // opt[ i ] = true

4.1 fence8 Fence Rails
  多维背包, 用DFSID先
  优化1 如果能够切k个木块, 那么最短的k个木块就能够切
  优化2 从长木板割先
优化3 第一个长度为L的木块从第i个木板割第二个从第j个木板割和反过来是一样的. 所以可以记录下来, 防止这类情况的发生.
优化4 如果一个木板和木块一样长就切他了
优化5 长度小于最短的木块的木板可以放弃了

4.1 cryptcow Cryptcowgraphy
  基本的方法是找到COW和没有处理的字串, 总共有9层递归.
  优化1 最终的字串的长度必然是47
  优化2 COW的个数一定相同
  优化3 COW中任两个的字串必然之前出现过
  优化4 加Hash
优化5 第一个字符到第一个C/O/W 的字串必然匹配原文的前面一部分后面也一样
优化6 第一个C/O/W 中必然是C 最后一个C/O/W必然是W

4.1 ariprog Arithmetic Progressions
预先生成平方表, 用计数排序排一下(O(n)的那种排序). 因为只要有前两个数就可以确定整个序列, 所以只需要枚举前两个数就可以了. 枚举时, 判断在范围内能否存在这种长度的序列, 然后再顺次判断. 输出的时候记得QuickSort一下.

4.2 ditch Drainage Ditches
Ford-Fulkerson就可以了, 由于边最多就200条, 用边集数组存储图. 注意可能会发生两点之间有几条边的情况…

4.2 stall4 The Perfect Stall
看出是二分图匹配的就做出来了…… 看不出的, 您现在看出了吧….

4.2 buylow Buy Low, Buy Lower
先作一个LIS 之后的DP方程:
T[k] = T[k] + T[j] // (data[k] > data[j]) /\ (len[k] = len[j + 1])

4.2 job Job Processing
AAAAAA-BBBB
AAA-----BBBBB
A机器从头到尾不许停, B机器从尾到头不许停. 将任务依次按照最有进行分配最后的总时间就是上面那两个串的长度.

4.2 frameup Frame Up
根据读入可以轻松的找到每个矩形的具体位置和大小, 也可以判断哪个矩形盖住了哪一个矩形. 如果一个矩形盖住了另一个矩形就把这个矩形引出一条有向边指向另一个. 再做一下拓扑排序.

4.3 prime3 the Primes
先生称所有符合条件的素数. 关键是搜索顺序, 总共24层搜索. 我的顺序是先搜最下面一排和最左边一列(这里面只会出现1379); 再搜对角线; 再搜第二列、第四列、第一行、第三行；剩下四个穷举. 注意第一行和第一列不会出现0. 还可以建一张映射表, 判断有无以某个数值开头的符合条件的素数. 但是我的这个方法得到的全是转置后的矩阵（这么说test1有两解？?）. 最后要记得排序哦. 我的test10是0.999s过的. 所以, 阿门…………………………..

4.3 prefix Longest Prefix
这个是个简单的DP吧. 拿个手指从字符串的第一位向后扫, 如果这一位能够完成, 就加上单词表里的所有单词, 把字符串加上单词后如果能够完成匹配, 字符串的这个位置也能够达到………………………………

4.3 cowcycle Cowcycles
搜的时候注意缩小范围, 相同的不会出现. 另外可以加上hash, 比方说2 6 10 14 与3 9 15 21, 事实上, 3 9 15 21可以被放弃了.

4.3 shopping Shopping Offers
有些有其他的商品的优惠可以去掉, 然后用6^5的枚举+记忆化就可以了.

4.3 race3 Street Race
Task1 先依次让每个点都假设不可避免, 然后DFS, 如果能够不访问这个点而到达终点那么这个点就是可避免的.
Task2 很显然这些点必然是不可避免的点. 然后先DFS一次, 把已访问的点标上Day1. 再DFS一次, 如果访问了Day1的点, 这个中点不可用.

4.4 spin Spinning Wheels
时间枚举到10000就可以了. 至于判断有没有5个裂缝重合, 可以用一个[0..359]的数组, 对于每一个轮子的裂缝部分的角度加一, 如果出现5的值就可行了.

4.4 ratio Feed Ratios
枚举100^3就可以了……

4.4 shuttle Shuttle Puzzle
可以找出规律, 把空位连成线就是一个递增/减2, 然后递增/减1的波浪形.

4.4 milk6 Pollutant Control
因为最小割 = 最大流. 所以求最大流先. 把边按照权递减的顺序排列, 权相等的按编号递增. 如果删除这个边, 流减少的就是边的容量, 这条边必须. 删除这个边后继续操作. 注意由于两点之间可以有多条边, 所以求最大流的时候把它们并作一条边, 输出的时候再分开就是了.

22:34 | 添加评论 | 固定链接 | 写入日志 | USACO

Splay Tree

{
A little bug:
It always destroys the balanced Tree.....
}

Type
    SplayTree = ^Node;
    Node = Record
              Value: Longint;
              Lc, Rc, P: SplayTree;
           End;

Var
Root: SplayTree;

Procedure Init(tmp: Longint);

Begin
New(Root);
Root^.Value := tmp;
Root^.Lc := Nil;
Root^.Rc := Nil;
Root^.P := Nil;
End;

Function Find(S: Longint; T: SplayTree): SplayTree;
// Try to Find the node whose Value equals S

Begin
If T = Nil Then
Exit(Nil);

If T^.Value < S Then
Exit(Find(S, T^.Rc));
If T^.Value > S Then
Exit(Find(S, T^.Lc));

Exit(T);
End;

Procedure Zig(T: SplayTree);
//Sift Up the First Left Child

Begin
Root^.Lc := T^.Rc;
If Root^.Lc <> Nil Then
Root^.Lc^.P := Root;
T^.Rc := Root;
T^.Rc^.P := T;
T^.P := Nil;
Root := T;
End;

Procedure Zag(T: SplayTree);
//Sift Up the First Right Child

Begin
Root^.Rc := T^.Lc;
If Root^.Rc <> Nil Then
Root^.Rc^.P := Root;
T^.Lc := Root;
T^.Lc^.P := T;
T^.P := Nil;
Root := T;
End;

Procedure ZigZig(T: SplayTree);
//Sift Up the Second Left Child

Var
Y, Z: SplayTree;

Begin
Y := T^.P;
Z := T^.P^.P;
If Z = Root Then
    Root := T
Else
    If Z^.P^.Lc = Z Then
      Z^.P^.Lc := T
    ELse
      Z^.P^.Rc := T;
T^.P := Z^.P;
Y^.P := T;
Z^.P := Y;
Y^.Lc := T^.Rc;
If Y^.Lc <> Nil Then
    Y^.Lc^.P := Y;
T^.Rc := Y;
Z^.Lc := Y^.Rc;
If Z^.Lc <> Nil Then
    Z^.Lc^.P := Z;
Y^.Rc := Z;
End;

Procedure ZagZag(T: SplayTree);
//Sift Up the Second Right Child

Var
Y, Z: SplayTree;

Begin
Y := T^.P;
Z := T^.P^.P;
If Z = Root Then
    Root := T
Else
    If Z^.P^.Lc = Z Then
      Z^.P^.Lc := T
    ELse
      Z^.P^.Rc := T;
T^.P := Z^.P;
Y^.P := T;
Z^.P := Y;
Y^.Rc := T^.Lc;
If Y^.Rc <> Nil Then
    Y^.Rc^.P := Y;
T^.Lc := Y;
Z^.Rc := Y^.Lc;
If Z^.Rc <> Nil Then
    Z^.Rc^.P := Z;
Y^.Lc := Z;
End;

Procedure ZigZag(T: SplayTree);
//Sift Up the Right Child's Left Child

Var
Y, Z: SplayTree;

Begin
Y := T^.P;
Z := Y^.P;
If Z = Root Then
    Root := T
Else
    If Z^.P^.Lc = Z Then
      Z^.P^.Lc := T
    Else
      Z^.P^.Rc := T;
T^.P := Z^.P;
Y^.P := T;
Z^.P := T;
Z^.Rc := T^.Lc;
If Z^.Rc <> Nil Then
    Z^.Rc^.P := Z;
Y^.Lc := T^.Rc;
If Y^.Lc <> Nil Then
    Y^.Lc^.P := Y;
T^.Lc := Z;
T^.Rc := Y;
End;

Procedure ZagZig(T: SplayTree);
//Sift Up the Left Child's Right Child

Var
Y, Z: SplayTree;

Begin
Y := T^.P;
Z := Y^.P;
If Z = Root Then
    Root := T
Else
    If Z^.P^.Lc = Z Then
      Z^.P^.Lc := T
    Else
      Z^.P^.Rc := T;
T^.P := Z^.P;
Y^.P := T;
Z^.P := T;
Z^.Lc := T^.Rc;
If Z^.Lc <> Nil Then
    Z^.Lc^.P := Z;
Y^.Rc := T^.Lc;
If Y^.Rc <> Nil Then
    Y^.Rc^.P := Y;
T^.Rc := Z;
T^.Lc := Y;
End;

Procedure Splay(T: SplayTree);
//Splay.... Ouch....

Begin
If T = Nil Then
    Exit;
While T <> Root Do
Begin
    If T^.P = Root Then
      If Root^.Lc = T Then
        Zig(T)
      Else
        Zag(T)
    Else
      If T^.P^.Lc = T Then
        If T^.P^.P^.Lc = T^.P Then
          ZigZig(T)
        Else
          ZigZag(T)
      Else
        If T^.P^.P^.Rc = T^.P Then
          ZagZag(T)
        Else
          ZagZig(T);
End;
End;

Procedure Ins(S: Longint);
//Insert a Node whose Value equals S

Var
T: SplayTree;

Begin
If Root = Nil Then
Begin
Init(S);
Exit;
End;

T := Root;

While true Do
Begin
If T = nil Then
Break;

    If T^.Value <= S Then
      If T^.Rc <> nil Then
        T := T^.Rc
      Else
        Begin
          New(T^.Rc);
          T^.Rc^.Value := S;
          T^.Rc^.P := T;
          T^.Rc^.Lc := nil;
          T^.Rc^.Rc := nil;
          Splay(T^.Rc);
          Break;
        End

    Else
      If T^.Lc <> nil Then
        T := T^.Lc
      Else
        Begin
          New(T^.Lc);
          T^.Lc^.Value := S;
          T^.Lc^.P := T;
          T^.Lc^.Lc := nil;
          T^.Lc^.Rc := nil;
          Splay(T^.Lc);
          Break;
        End;
End;
End;

Function Max(T: SplayTree): SplayTree;
//get the maximum node in the tree whose root is T
Begin
While T^.Rc <> Nil Do
T := T^.Rc;
Exit(T);
End;

Procedure Del(S: Longint);
//Delete a Node whose Value equals S

Var
T, tmp: SplayTree;

Begin
T := Find(S, Root);
If T = Nil Then
Exit;

If (T^.Lc = Nil) Then
// no left child

If (T^.Rc = Nil) Then
// it's the leaf

      If T^.P = Nil Then
        Root := Nil
      Else
      Begin
        If T^.P^.Lc = T Then
          T^.P^.Lc := Nil
        Else
          T^.P^.Rc := Nil;
      End

    Else
      //only right child
      If T^.P = Nil Then
      Begin
        Root := T^.Rc;
        T^.Rc^.P := Nil;
      End
      Else
        If T^.P^.Lc = T Then
        Begin
          T^.P^.Lc := T^.Rc;
          T^.Rc^.P := T^.P;
        End
        Else
          Begin
            T^.P^.Rc := T^.Rc;
            T^.Rc^.P := T^.P;
          End

    // have left child
    Else
      If (T^.Rc = Nil) Then
      //only left child
        If T^.P = Nil Then
        Begin
          Root := T^.Lc;
          T^.Lc^.P := Nil;
        End
        Else
          If T^.P^.Lc = T Then
          Begin
             T^.P^.Lc := T^.Lc;
             T^.Lc^.P := T^.P;
          End
          Else
            Begin
              T^.P^.Rc := T^.Lc;
              T^.Lc^.P := T^.P;
            End
      Else
      // both left and right child
      Begin
        tmp := Max(T^.Lc);

        If Root = T Then
        Begin
          Root := T^.Lc;
          Root^.P := Nil;
        End
        Else
          Begin
            T^.Lc^.P := T^.P;
            If T^.P^.Lc = T Then
              T^.P^.Lc := T^.Lc
            Else
              T^.P^.Rc := T^.Lc;
          End;

        tmp^.Rc := T^.Rc;
        T^.Rc^.P := tmp;
        Splay(tmp);
      End;

End;

Procedure Mid_Visit(T: SplayTree);

Begin
If T = Nil Then
    Exit;
If T^.Lc <> Nil Then
    Mid_Visit(T^.Lc);
   write(T^.Value,' ');
If T^.Rc <> Nil Then
    Mid_visit(T^.Rc);
End;

Procedure Main;
//Do whatever you wanna do
Var
i, tmp, n, m: Longint;

Begin
assign(input,'data.in');
reset(input);
read(n);
For i := 1 To n Do
Begin
Read(tmp);
Ins(tmp);
End;

Read(m);
For i := 1 To m Do
Begin
Read(tmp);
Del(tmp);
End;

assign(output,'data.out');
rewrite(output);
Mid_Visit(Root);
close(output);
End;

Begin
Main;
End.

1月31日

写Splay Tree

写Splay Tree ing

Failing....

21:38 | 添加评论 | 固定链接 | 写入日志

写了一个Treap

Type
Treap = ^Node;
Node = Record
           Rank, Value: longint;
           Lc, Rc, P: Treap;
         End;
Var
T, Root: Treap;
n, m: longint;

Function Random_Rank: longint;
// Give the Rank to each node of the Treap

Begin
exit((random(1000000)) mod n);
End;

Procedure Init(tmp: longint);
//Initialize The Root

Begin
Randomize;
New(Root);
Root^.P := nil;
Root^.Rank := Random_Rank;
Root^.Lc := nil;
Root^.Rc := nil;
Root^.Value := tmp;
End;

Procedure Rotation_Left(T: Treap);
// Sift Up the Left Child

Var
tmp: Treap;

Begin
If T = Nil Then
    Exit;
tmp := T^.P;
tmp^.Lc := T^.Rc;
If T^.Rc <> nil Then
    T^.Rc^.P := tmp;
T^.Rc := tmp;
If tmp^.P <> nil Then
If tmp^.P^.Lc = tmp Then
    tmp^.P^.Lc := T
Else
    tmp^.P^.Rc := T;
T^.P := tmp^.P;
tmp^.P := T;
If T^.P = Nil Then
    Root := T;
End;

Procedure Rotation_Right(T: Treap);
// Sift Up the Right Child

Var
tmp: Treap;

Begin
If T = Nil Then
    Exit;
tmp := T^.P;
tmp^.Rc := T^.Lc;
If T^.Lc <> nil Then
    T^.Lc^.P := tmp;
T^.Lc := tmp;
If tmp^.P <> nil Then
If (tmp^.P^.Rc = tmp) Then
    tmp^.P^.Rc := T
Else
    tmp^.P^.Lc := T;
T^.P := tmp^.P;
tmp^.P := T;
If T^.P = Nil Then
    Root := T;
End;

Procedure Turn(T: Treap);
//Turn the Treap In order to settle the node to the right place

Begin
While (T^.P <> Nil) And (T^.Rank < T^.P^.Rank) Do
    If T^.P^.Lc = T Then
      Rotation_Left(T)
    Else
      Rotation_Right(T);
end;

Procedure Ins(S: longint);
// insert a node

Var
tmp: Treap;

Begin
If Root = Nil Then
Begin
Init(S);
Exit;
End;

tmp := Root;

While true Do
Begin
If tmp = nil Then
Break;

    If tmp^.Value <= S Then
      If tmp^.Rc <> nil Then
        tmp := tmp^.Rc
      Else
        Begin
          New(tmp^.Rc);
          tmp^.Rc^.Value := S;
          tmp^.Rc^.P := tmp;
          tmp^.Rc^.Lc := nil;
          tmp^.Rc^.Rc := nil;
          tmp^.Rc^.Rank := Random_Rank;
          Turn(tmp^.Rc);
          Break;
        End

    Else
      If tmp^.Lc <> nil Then
        tmp := tmp^.Lc
      Else
        Begin
          New(tmp^.Lc);
          tmp^.Lc^.Value := S;
          tmp^.Lc^.P := tmp;
          tmp^.Lc^.Lc := nil;
          tmp^.Lc^.Rc := nil;
          tmp^.Lc^.Rank := Random_Rank;
          Turn(tmp^.Lc);
          Break;
        End;
End;
End;

Function Find(S: longint; T: Treap): Treap;
// Try to Find the node whose value equals S

Begin
If T = Nil Then
Exit(Nil);

If T^.Value > S Then
Exit(Find(S, T^.Lc));
If T^.Value < S Then
Exit(Find(S, T^.Rc));

Exit(T);
End;

Procedure Del(S: longint);
//delete a node

Var
tmp: Treap;

Begin
tmp := Find(S, Root);
If tmp = Nil Then
Exit;

tmp^.Rank := MaxLongint;

While (tmp^.Lc <> Nil) Or (tmp^.Rc <> Nil) Do
Begin
    If (tmp^.Lc <> Nil) Then
      Turn(tmp^.Lc);
    If (tmp^.Rc <> Nil) Then
      Turn(tmp^.Rc);
End;

If tmp^.P = Nil Then
    Root := Nil
Else
    If tmp^.P^.Lc = tmp Then
      tmp^.P^.Lc := Nil
    Else
      tmp^.P^.Rc := Nil;
End;

Procedure Mid_Visit(T: Treap);
// Visit the Treap in order to chk the correctness

Begin
If T = Nil Then
    Exit;
If T^.Lc <> nil Then
    Mid_Visit(T^.Lc);
write(T^.Value,' ');
If T^.Rc <> nil Then
    Mid_Visit(T^.Rc);
End;

Procedure Main;
//Do whatever you wanna do

Var
i, tmp: longint;

Begin
assign(input,'data.in');
reset(input);
read(n);

For i := 1 To n Do
Begin
read(tmp);
Ins(tmp);
End;

read(m);
For i := 1 To m Do
Begin
read(tmp);
Del(tmp);
End;
close(input);

assign(output,'data.out');
rewrite(output);
Mid_Visit(Root);
close(output);
End;

Begin
Main;
End.

11:55 | 添加评论 | 固定链接 | 写入日志

1月29日