1656: [Usaco2006 Jan] The Grove 树木 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 143 Solved: 88 [Submit][Status][Discuss] Description The pasture contains a small, contiguous grove of trees that has no 'holes' in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting …

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 cow …

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 451 Solved: 226 [Submit][Status][Discuss] Description 考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'x'。例如下图： . . B x . . x x A . . . . x . . x . . . . . x . . 贝茜发现自己恰好在点A处，她想去B处的盐块舔盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管 …

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 ) 正方形格子的 。某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。 贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。她希望在莲花上一个一个的跳，目标是另一 …

1627: [Usaco2007 Dec]穿越泥地 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 624 Solved: 411 [Submit][Status][Discuss] Description 清早6：00，Farmer John就离开了他的屋子，开始了他的例行工作：为贝茜挤奶。前一天晚上，整个农场刚经受过一场瓢泼大雨的洗礼，于是不难想见，FJ 现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标(0, 0)的位置，贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。当然咯， FJ也看到了地上的 …

1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 661 Solved: 292 [Submit][Status][Discuss] Description The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows. He wonders how many guards he will need if he wishes …

1611: [Usaco2008 Feb]Meteor Shower流星雨 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1239 Solved: 537 [Submit][Status][Discuss] Description 去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息： 一场流星雨即将袭击整个霸中，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽， 届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，芙蓉哥哥开始担心自己的 安全问题。以霸中至In型男名誉起誓，他一定要在被流星砸到前，到达一个安全的地方 （也就是说，一块不会被任何流星砸到的土地）。如 …

Description N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。 Input *第一行：两个被空格隔开的整数：N和Q *第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI *第n+1行到n+Q …

题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。 当时比赛一种都不会。 先说一种：做法是把格子看成点，可以到达的相邻格子之间看成有边相连，然后倒过来用并查集判断无向图的连通性。具体做法是：先统计初始所有空的位置，然后把所有要增加的山都加上（先统计空的位置是因为山之后要去掉，而去掉以后要得到该点的标号），然后将把所有空的点以及china(设标号为n*m+1)点,和india(**设标号为n*m+2) **点通过并查集来合并..可以从上往下从左往右，每次只需要判断上面的点和左边的点是否有空，如果有就用并查集合并。 china点和india点特殊搞就好。 然后判断india和china是否联通，如 …

做过一道类似的题 因为是问最短，很容易想到是bfs 对于点x，可以到达点x-1,和点2*x 需要注意的是上界限。 并不是max(m,n) 因为可能先达到比m大，之后再减回来的情况是更优的。 max(2m,2n)肯定是足够的 /************************************************************************* > File Name: code/cf/#295/B.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月17日 星期一 04时16分51 …