传送门：【UVALive】5713 Qin Shi Huang's National Road System 题目大意：秦朝有n个城市，需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路，不花钱，也不用劳动力，但只能修一条路，因此需要慎重选择用法术修哪一条路。秦始皇不仅希望其他道路的总长度B尽量短（这样可以节省劳动力），还希望法术连接的两个城市的人口之和A尽量大，因此下

题目链接：uva 1494 - Qin Shi Huang's National Road System 建成最小生成树之后，枚举两节点，然后删除路径上权值上最大的边。 #include <cstdio>#include <cstring>#include <cmath>#include <vector>#include <algorithm>using namespa

链接： http://acm.hdu.edu.cn/showproblem.php?pid=4081 题目： Problem Description During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China ---- they

现场其实想到了找两点间最大边，但是一直在想DFS找的方法，期间我也想了想预处理的可行性，可是想岔道了，觉得不可行，结果今天用类似DP的预处理终于给过了，我擦了，铁牌第一名，要多点背有多点背。莫非是RP用光了，希望明年能好点吧。 Run ID Problem ID Status Time Memory Language Code Submit At User 15470

https://vjudge.net/problem/HDU-4081 给定你一个图，和每个点的坐标，问你建设n-1条路将它们链接起来后，可以减去其中一条边的花费，设其剩下的花费为B。而这条边对应的两个点的 点权大小为 A 要求A/B尽可能的大。。 思路： 这是用prim求次小生成树的方法。 维护path[][],作为表示i到在MST上的最长边。 并且 在一个最小生成树中，加一个边，一