题目描述
某国有n个城市,它们互相之间没有公路相通,因此交通十分不便。为解决这一“行路难”的问题,政府决定修建公路。修建公路的任务由各城市共同完成。
修建工程分若干轮完成。在每一轮中,每个城市选择一个与它最近的城市,申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
政府审批的规则如下:
(1)如果两个或以上城市申请修建同一条公路,则让它们共同修建;
(2)如果三个或以上的城市申请修建的公路成环。如下图,A申请修建公路AB,B申请修建公路BC,C申请修建公路CA。则政府将否决其中最短的一条公路的修建申请;
(3)其他情况的申请一律同意。
一轮修建结束后,可能会有若干城市可以通过公路直接或间接相连。这些可以互相:连通的城市即组成“城市联盟”。在下一轮修建中,每个“城市联盟”将被看作一个城市,发挥一个城市的作用。
当所有城市被组合成一个“城市联盟”时,修建工程也就完成了。
你的任务是根据城市的分布和前面讲到的规则,计算出将要修建的公路总长度。
题解
本题从第一条、城市联盟、选择最近的城市都可以看出最小生成树,关键在于第二条。我们考虑何时会出现第二条的情况。我们应当对每一个点相连的边长间的相对关系入手。设三角形边长为$a,b,c$,若成一个环,则$a\leq b,b\leq c,c\leq a\cdots$不对!$a$不可能小于$a$!所以第二种情况根本不可能存在。所以最小生成树即可。
#include#include #include #include using namespace std;const int MAX_NODE = 5010;const double INF = 1e18;int TotNode;double MinLen[MAX_NODE];bool InTree[MAX_NODE];struct Coor{ int X, Y;}_coors[MAX_NODE];double Dist(const Coor& a, const Coor& b){ double dx = b.X - a.X, dy = b.Y - a.Y; return sqrt(dx * dx + dy * dy);}double Prim(){ double ans = 0; InTree[1] = true; for (int i = 2; i <= TotNode; i++) MinLen[i] = Dist(_coors[1], _coors[i]); int cnt = 1; while (cnt <= TotNode - 1) { int u; double minLen = INF; for (int i = 1; i <= TotNode; i++) if (!InTree[i] && MinLen[i] < minLen) { minLen = MinLen[i]; u = i; } if (minLen == INF) return -1; cnt++; ans += minLen; InTree[u] = true; for (int v = 1; v <= TotNode; v++) if (!InTree[v]) MinLen[v] = min(MinLen[v], Dist(_coors[u], _coors[v])); } return ans;}int main(){ scanf("%d", &TotNode); for (int i = 1; i <= TotNode; i++) scanf("%d%d", &_coors[i].X, &_coors[i].Y); printf("%.2f\n", Prim()); return 0;}