转载自： 原文链接
树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式也是多样的，所以不同的遍历会得到不同的DFS树，进而产生不同的树边，前向边，后向边，横叉边。所以这4种边，是一个相对的概念。 在图的遍历中，往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义 vis = 0,表示该顶点没没有被访问 vis = 1,表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回 vis = …
阅读更多1652: [Usaco2006 Feb]Treats for the Cows
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 290 Solved: 226 [Submit][Status][Discuss]
Description
FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he …
阅读更多1650: [Usaco2006 Dec]River Hopscotch 跳石子
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 440 Solved: 290 [Submit][Status][Discuss]
Description
Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, …
阅读更多Time Limit: 5 Sec Memory Limit: 64 MB Submit: 504 Solved: 265 [Submit][Status][Discuss]
Description
The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 …
阅读更多1646: [Usaco2007 Open]Catch That Cow 抓住那只牛
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 915 Solved: 441 [Submit][Status][Discuss]
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 <= N <= 100,000) on a number line and the …
阅读更多1643: [Usaco2007 Oct]Bessie’s Secret Pasture 贝茜的秘密草坪
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 330 Solved: 278 [Submit][Status][Discuss]
Description
农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他已经把草皮放在了一个奶牛贝茜已经知道的地方。 贝茜总是希望把美味的草皮放到她的秘密庄园里，她决定从这些草皮中取出恰好4块搬到她的秘密庄园中，然后把它们分成1×1的小块，组成一个 …
阅读更多Time Limit: 5 Sec Memory Limit: 64 MB Submit: 667 Solved: 389 [Submit][Status][Discuss]
Description
贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N (1 ≤ N ≤ 1,000,000)个小时，标记为0..N-1。 Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间(0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 < 结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从 …
阅读更多1641: [Usaco2007 Nov]Cow Hurdles 奶牛跨栏
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 531 Solved: 344 [Submit][Status][Discuss]
Description
Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台，分别标记为1..N。所有站台之间有M (1 ≤ M ≤ 25,000)条 …
阅读更多1640: [Usaco2007 Nov]Best Cow Line 队列变换
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 710 Solved: 373 [Submit][Status][Discuss]
Description
FJ打算带着他可爱的N (1 ≤ N ≤ 2,000)头奶牛去参加”年度最佳老农”的比赛.在比赛中,每个农夫把他的奶牛排成一列,然后准备经过评委检验. 比赛中简单地将奶牛的名字缩写为其头字母(the initial letter of every cow),举个例子,FJ带了Bessie, Sylvia,和Dora,那么就可以缩写为BSD. FJ只需将奶 …
阅读更多1639: [Usaco2007 Mar]Monthly Expense 月度开支
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 767 Solved: 381 [Submit][Status][Discuss]
Description
Farmer John是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每个月的正常运转的。他已经计算了他以后N(1<=N<=100,000)个工作日中每一天的花费moneyi(1<=moneyi<=10,000)，他想要为他连续的M(1<=M<=N)个被叫做“清算月”的结帐时期做一 …
阅读更多1637: [Usaco2007 Mar]Balanced Lineup
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 503 Solved: 336 [Submit][Status][Discuss]
Description
Farmer John 决定给他的奶牛们照一张合影，他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线，每头牛都有它的坐标(范围: 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛 …
阅读更多1635: [Usaco2007 Jan]Tallest Cow 最高的牛
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 472 Solved: 278 [Submit][Status][Discuss]
Description
FJ’s N (1 <= N <= 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only …
阅读更多1634: [Usaco2007 Jan]Protecting the Flowers 护花
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 605 Solved: 383 [Submit][Status][Discuss]
Description
Farmer John went to cut some wood and left N (2 <= N <= 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cows were in his …
阅读更多1632: [Usaco2007 Feb]Lilypad Pond
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 496 Solved: 153 [Submit][Status][Discuss]
Description
Farmer John 建造了一个美丽的池塘，用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。 贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。她希望在莲花上一个一个的跳，目标是 …
阅读更多2023: [Usaco2005 Nov]Ant Counting 数蚂蚁
Time Limit: 4 Sec Memory Limit: 64 MB Submit: 149 Solved: 85 [Submit][Status][Discuss]
Description
有一天，贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物．很快贝茜发现有些蚂蚁长得几乎一模一样，于是她认为那些蚂蚁是兄弟，也就是说它们是同一个家族里的成员．她也发现整个蚂蚁群里有时只有一只出来觅食，有时是几只，有时干脆整个蚁群一起出来．这样一来，蚂蚁们出行觅食时的组队方案就有很多种．作为一头有数学头脑的奶牛，贝茜注意到整个蚂蚁群由T(1≤T≤1000) …
阅读更多1629: [Usaco2007 Demo]Cow Acrobats
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 771 Solved: 398 [Submit][Status][Discuss]
Description
Farmer John’s N (1 <= N <= 50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging …
阅读更多