交付:五条验收一起过

七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b。 最后一步:把五条验收条款补全,一次全部验过。每一条都落在一个唯一的数上——顺序可以不同,但这些数不能不同。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

大图递归会出什么事

在实验机上对一条十万个点的链做递归 DFS,程序最可能【0】。

开始练习 →

补写 Kahn 拓扑排序

场景:实验机上 ~/work/graph/topo.cpp 读入一张有向图,要输出编号最小优先的拓扑序;有环就输出 有环。topo 函数还空着。 任务:补全 topo。make 编译,./topo < sample.txt 自测。ch

开始练习 →

十万点的图别爆栈

场景:~/work/graph/scc.cpp 用递归 Tarjan 求强连通分量个数和最大分量大小。小图没问题,可点一多、链一长就段错误。check 会在 1 MB 栈下运行,并限时 2 秒。 任务:把递归改成手写栈(或换成两遍都用手写栈

开始练习 →

实现最大流

场景:~/work/graph/flow.cpp 读入一张带容量的有向图,要输出从 1 号到 n 号的最大流。maxflow 还空着。 任务:补全 maxflow(Edmonds-Karp 或 Dinic 都行)。make 编译后用 sam

开始练习 →

修好判环的条件

场景:~/work/graph/cycle.cpp 用 Kahn 判断一张有向图有没有环,可有的无环图被判成了有环,有的有环图又被放过了。 任务:修好判环那一行。make 编译后用 sample.txt 自测;check 会用随机的有环 /

开始练习 →

找出按出度排序的反例

场景:~/work/graph/badtopo.cpp 声称「按出度从大到小排,就是一个拓扑序」。这个说法是错的。 任务:构造一张无环有向图,让 badtopo 排出来的顺序违反其中某条边,写进 ~/work/graph/answer.tx

开始练习 →

邻接表的边节点要还回去

场景:~/work/graph/adj.cpp 用链表存邻接表,每读一组数据就 new 出一批边节点。输出是对的,可 Makefile 带了内存检查,一跑就报内存泄漏。 任务:修好 clear:把每个点挂着的边节点都 delete 掉。ma

开始练习 →

查找和匹配要回答的事差在哪

第 1 步:文本 8 个字,要找 abc 第 2 步:起点 0:没对上,挪一格 第 3 步:起点 1:没对上,挪一格 第 4 步:起点 2:三个连着都对上 第 5 步:起点 3:没对上,挪一格 第 6 步:起点 4:没对上,挪一格 第 7

开始练习 →

匹配的结果该给出什么(C++)

一个模式在一段文本里找完之后,该交出来的结果是【0】。

开始练习 →