Articles in the category of 最小生成树

洛谷 P1546 最短网络 Agri-Net 最小生成树

洛谷 P1546 最短网络 Agri-Net 最小生成树题目背景农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。题目描述约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案...

子不语 August 7, 2019 No comments

洛谷 P1536 村村通最小生成树

洛谷 P1536 村村通最小生成树题目描述某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？输入格式每个输入文件包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目N（N<...

子不语 May 2, 2019 No comments

hdu1102 Constructing Roads prim最小生成树

hdu1102 Constructing Roads prim最小生成树There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village ...

子不语 April 11, 2019 No comments

洛谷P1547 Out of Hay 最小生成树

洛谷P1547 Out of Hay 最小生成树题目背景奶牛爱干草题目描述Bessie 计划调查N (2 <= N <= 2,000)个农场的干草情况，它从1号农场出发。农场之间总共有M (1 <= M <= 10,000)条双向道路，所有道路的总长度不超过1,000,000,000。有些农场之间存在着多条道路，所有的农场之间都是连通的。Bessie希望计算出该图中最...

子不语 February 14, 2019 No comments

洛谷p1111 修复公路最小生成树

洛谷p1111 修复公路最小生成树题目背景AA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。题目描述给出A地区的村庄数NN，和公路数MM，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）输入格式第11行两...

子不语 December 12, 2018 No comments