交付:五条验收一起过
七个构建任务编号 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】。