# [USACO12FEB] Overplanting S ## 题目描述 Farmer John has purchased a new machine that is capable of planting grass within any rectangular region of his farm that is "axially aligned" (i.e., with vertical and horizontal sides). Unfortunately, the machine malfunctions one day and plants grass in not one, but N (1 <= N <= 1000) different rectangular regions, some of which may even overlap. Given the rectangular regions planted with grass, please help FJ compute the total area in his farm that is now covered with grass. 在一个笛卡尔平面坐标系里（则X轴向右是正方向，Y轴向上是正方向），有N($1<=N<=1000$)个矩形，第i个矩形的左上角坐标是(x1, y1),右下角坐标是（x2,y2）。问这N个矩形所覆盖的面积是多少？注意：被重复覆盖的区域的面积只算一次。 ## 输入格式 第一行，一个整数Ｎ。 ($1<=N<=1000$)。 接下来有N行，每行描述一个矩形的信息，分别是矩形的x1、y1、x2、y2。 其中 $-10^8<=x1,y1,x2,y2<=10^8$。 ## 输出格式 一个整数，被N个矩形覆盖的区域的面积。 ## 样例 #1 ### 样例输入 #1 ``` 2 0 5 4 1 2 4 6 2 ``` ### 样例输出 #1 ``` 20 ```

这是一个计算矩形覆盖面积的问题。题目给出了N个矩形的坐标信息，需要计算这些矩形的覆盖面积。

算法思路如下：

1. 创建两个集合，分别保存矩形的x坐标和y坐标。
2. 遍历每个矩形，将矩形的x坐标和y坐标添加到对应的集合中。
3. 对x坐标和y坐标进行排序。
4. 遍历排序后的x坐标和y坐标，计算相邻两个坐标之差，并累加到总面积中。

具体实现可以参考以下代码：

相关问题

[Usaco2007 Feb]Cow Party

### 回答1：
题目描述

有N头奶牛，它们在M个牛棚之间相互转移。每个牛棚里有一些奶牛，每分钟可以容纳一头奶牛。一头奶牛从一个牛棚走到另一个牛棚需要一分钟的时间。现在，这些奶牛要开一个牛派对，它们要在同一时间到达同一个牛棚，所以它们需要在某个牛棚等待一段时间。你需要计算最小的等待时间，使得所有奶牛都能够在同一时间到达同一个牛棚。

输入格式

第一行包含三个整数N，M，X。

接下来M行，每行包含三个整数a，b，t，表示牛棚a和牛棚b之间有一条双向边，需要t分钟才能通过。

输出格式

输出一个整数，表示最小等待时间。

数据范围

1≤N≤500
1≤M≤10000
1≤X≤N
1≤a,b≤N
1≤t≤1000

输入样例#1

3 3 1
1 2 5
2 3 5
1 3 10

输出样例#1

5

输入样例#2

4 5 4
1 2 10
2 3 10
3 4 10
4 1 10
1 3 20

输出样例#2

30

算法1

(最短路) $O(N^3)$

Dijkstra算法
Dijkstra（迪杰斯特拉）算法是由荷兰计算机科学家狄克斯特拉于1956年发明的，因此又叫狄克斯特拉算法。

Dijkstra算法是一种贪心算法，用于求解一个节点到其他所有节点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。

具体做法是：设立一个数组dis来保存源点到各个顶点的最短距离和一个数组book[i]来记录一个顶点是否已经在队列中。

初始时，原点s的路径权重被赋为0 （dis[s] = 0）。若对于顶点s存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，所有顶点并不属于任何已知最短路径所包含的顶点集合，因此都被标记为未知最短路径长度。当算法结束时，dis[v]中存储的便是源点s到顶点v的最短路径，或者如果从s无法到达v，则值为INF。
Dijkstra算法流程：

算法流程：
1. 将所有顶点分为两部分：已知最短路的顶点集合P和未知最短路的顶点集合Q。
2. 初始时，顶点集合P中只有源点s一个元素，以源点s为起点向外扩展。
3. 每次从顶点集合Q中选取一个顶点u（u的dist最小），并加入到顶点集合P中，同时以u为中心进行扩展。
4. 重复步骤3，直到顶点集合Q为空或者终点被加入到顶点集合P中。
5. 算法结束，最短路径保存在dis数组中。

时间复杂度

Dijkstra算法的时间复杂度为O(N^2)。由于N较小，因此可以通过本题。

参考文献

Dijkstra算法讲解

C++ 代码

算法2

(最短路) $O(N^2)$

Floyd算法
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

Floyd算法的基本思想

设G=(V,E)是一个带权有向图，其邻接矩阵为W。V={v1,v2,……,vn}，W[1:n,1:n]，则该图的Floyd算法可描述如下：

时间复杂度

Floyd算法的时间复杂度为O(N^3)。由于N较小，因此可以通过本题。

参考文献

Floyd算法讲解

C++ 代码

算法3

(最短路) $O(N^2)$

Bellman-Ford算法
Bellman-Ford算法是一种单源最短路径算法，可以处理负权边，但不能处理负权回路。

Bellman-Ford算法的基本思想

对于图中的任意一条边(u, v)，Bellman-Ford算法会对每一条边进行一次松弛操作（Relax），并且这些操作是按照顺序进行的：当算法进行第i次松弛操作时，它只会改变长度为i+1的路径上的顶点的值。因此，当算法执行完第n-1次松弛操作后，路径长度最长不超过n-1，此时所有最短路径都已经求出。

时间复杂度

Bellman-Ford算法的时间复杂度为O(N*M)。由于N和M的范围较小，因此可以通过本题。

参考文献

Bellman-Ford算法讲解

C++ 代码

### 回答2：
Usaco 2007 Feb的问题是关于Cow Party的。这个问题中，农夫约翰有N头奶牛，它们之间通过一些路径相互连接，并且每个路径都有一个长度。约翰想要在某个时间将它的所有奶牛聚集在一起举办一个派对，现在他想知道所有奶牛从各自的位置到达聚会地点所需的最短时间。

为了解决这个问题，我们可以使用Dijkstra算法。我们首先需要创建一个节点集合，包含所有的奶牛和派对地点，并且初始化每个节点的最短时间为无穷大。接下来，我们选取一个起点节点--聚会地点，并将它的最短时间设置为0。然后我们开始遍历所有的节点，每次选择一个最短时间未确定的节点，并更新它的邻居节点的最短时间。我们重复这个过程，直到所有节点的最短时间都确定。

在更新节点的最短时间时，我们需要根据节点之间的路径长度来更新。我们检查从当前节点到邻居节点的路径长度加上当前节点的最短时间是否小于邻居节点目前的最短时间。如果是，则更新邻居节点的最短时间为新的最短时间。

最后，我们可以得到所有奶牛到达聚会地点所需的最短时间。我们找到所有奶牛起始位置的最长最短时间，即为我们的答案。

通过使用Dijkstra算法，我们可以解决这个问题并得到最优解。因此，Usaco 2007 Feb的Cow Party问题可以通过这种方法解决。

B3445 [Usaco2014 Feb] Roadblock

这道题是一道典型的最短路问题，可以使用Dijkstra算法或者Floyd算法来解决。

首先，我们需要构建一个有向图，每个节点代表一个城市，每条边代表两个城市之间的道路。题目中给出了每条边的长度，我们可以将其作为边的权值。

接下来，我们需要找到从起点到终点的最短路径。如果没有路障的限制，我们可以直接使用Dijkstra算法或者Floyd算法来求解。但是，由于题目中给出了一个路障，我们需要先去除这个路障，重新计算最短路径，然后再将路障加回去，再次计算最短路径。最后，将两次计算得到的最短路径加起来，就是我们所求的答案。

具体实现时，我们可以使用Dijkstra算法或者Floyd算法来计算最短路径，使用一个数组来记录每个节点到起点的最短距离。对于去除路障的情况，我们可以将路障的边的权值加上一个足够大的数，比如10000，表示这条路不通。对于重新计算最短路径的情况，我们可以使用相同的算法，只不过这次路障是通的。

最后，将两次计算得到的最短路径加起来，就是我们所求的答案。