HBC20380[SDOI2015]道路修建题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

某国有2N个城市，这2N个城市构成了一个2行N列的方格网， 现在该国政府有一个旅游发展计划，这个计划需要选定L、R两列(L ≤ R)，修建若干条专用道路，使得这两列之间（包括这两列）的所有2(R-L+1)个城市中每个城市可以只通过专用道路就可以到达这2(R-L+1)个城市中的任何一个城市， 这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建，且修建需要花费一定的费用

某国有2N个城市，这2N个城市构成了一个2行N列的方格网。 现在该国政府有一个旅游发展计划，这个计划需要选定L、R两列(L ≤ R)，修建若干条专用道路，使得这两列之间（包括这两列）的所有2(R-L+1)个城市中每个城市可以只通过专用道路就可以到达这2(R-L+1)个城市中的任何一个城市。 这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建，且修建需要花费一定的费用。 由于该国政府决定尽量缩减开支，因此政府决定，选定L、R后，只修建2(R-L+1)-1条专用道路，使得这些专用道路构成一个树结构。 现在你需要帮助该国政府写一个程序，完成这个任务。具体地，该任务包含M个操作，每个操作的格式如下：  1.C x0 y0 x1 y1 w：由于重新对第x0行第y0列的城市和第x1行第y1列的城市之间的情况进行了考察，它们之间修建一条专用道路的花费变成了w； 2.Q L R：若政府选定的两列分别为L、R，询问政府的最小开支。

标签： HBC20380[SDOI2015]道路修建题解