HDU 1233 还是畅通工程（最小生成树）
传送门还是畅通工程Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 41447 Accepted Submission(s): 1892...
HDU 1875 畅通工程再续 (最小生成树)
畅通工程再续Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 17913 Accepted Submission(s): 5593Pro...
Constructing Roads（1102 最小生成树 prim）
Constructing RoadsTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 18256 Accepted Submission...
ACM第四站————最小生成树（普里姆算法）
对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。普里姆算法是以其中某一顶点为起点，逐步寻找各个顶点上最小权值的边来构建最小生成树。其中运用到了回溯，贪心的思想。----------2018年5月24日补：#begin根据定义我们...
AT2134 Zigzag MST 最小生成树
正解:最小生成树解题报告:先放下传送门QAQ然后这题,首先可以发现这神奇的连边方式真是令人头大,,,显然要考虑转化掉QAQ大概看一下可以发现点对的规律是,左边++,交换位置,再仔细想下,就每个点会连上相邻两点,也就相邻两点会通过另外一个点连边首先可以发现加到后来已经是麻油意义的了,想下kruscal...
【BZOJ 1016】【JSOI 2008】最小生成树计数
http://www.lydsy.com/JudgeOnline/problem.php?id=1016统计每一个边权在最小生成树中使用的次数，这个次数在任何一个最小生成树中都是固定的（归纳证明）。在同一个边权上对所有边权为这个的边暴力统计（可以用矩阵树定理），然后用并查集把这个边权的所有边贡献的连...
HDU1879--继续畅通工程（最小生成树）
Problem Description省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。In...
poj 3522 Slim Span (最小生成树kruskal)
http://poj.org/problem?id=3522Slim SpanTime Limit: 5000MS Memory Limit: 65536KTotal Submissions: 5666 Accepted: 2965DescriptionGiven an undirected wei...
hdu 1233(还是畅通project)（prime算法，克鲁斯卡尔算法）（并查集，最小生成树）
还是畅通projectTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 26860 Accepted Submission(s): 11...
bzoj 2594 [Wc2006]水管局长数据加强版（LCT+最小生成树）
【深坑勿入】【给个链接】http://blog.csdn.net/popoqqq/article/details/41348549 #include<cstdio> #include<cstring> #include<iostream> #include<...
CSP 地铁修建 Kruskal (最小生成树+并查集)
问题描述A市有n个交通枢纽，其中1号和n号非常重要，为了加强运输能力，A市决定在1号到n号枢纽间修建一条地铁。地铁由很多段隧道组成，每段隧道连接两个交通枢纽。经过勘探，有m段隧道作为候选，两个交通枢纽之间最多只有一条候选的隧道，没有隧道两端连接着同一个交通枢纽。现在有n家隧道施工的公司，每段候选的隧...
POJ 2031 Building a Space Station【经典最小生成树】
链接：http://poj.org/problem?id=2031http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22013#problem/ABuilding a Space StationTime Limit: 1000MS Memor...
POJ 2031 Building a Space Station【最小生成树+简单计算几何】
You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write ...
poj 2031 Building a Space Station（最小生成树，三维，基础）
只是坐标变成三维得了，而且要减去两边的半径而已题目//最小生成树，只是变成三维的了#define _CRT_SECURE_NO_WARNINGS#include<stdlib.h>#include<stdio.h>#include<iostream>#inclu...
POJ2031 Building a Space Station【最小生成树】
题意：就是给出三维坐标系上的一些球的球心坐标和其半径，搭建通路，使得他们能够相互连通。如果两个球有重叠的部分则算为已连通，无需再搭桥。求搭建通路的最小边长总和是多少。思路：先处理空间点之间的距离，要注意的是两个球面相交的情况，相交的话距离是0。两球面距离是球心距离减去两个球的半径（边权 = AB球面...
poj 2031 Building a Space Station【最小生成树prime】【模板题】
Building a Space StationTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 5699 Accepted: 2855DescriptionYou are a member of the space station ...
最小生成树——Prim算法和Kruskal算法
洛谷P3366 最小生成树板子题这篇博客介绍两个算法：Prim算法和Kruskal算法，两个算法各有优劣一般来说当图比较稀疏的时候，Kruskal算法比较快而当图很密集，Prim算法就大显身手了下面是这两种算法的介绍Prim算法百度百科定义：传送门好吧，其实当我第一眼看到这个东西的时候感觉和Dijk...
POJ - 3026 Borg Maze BFS加最小生成树
Borg Maze题意：题目我一开始一直读不懂。有一个会分身的人，要在一个地图中踩到所有的A，这个人可以在出发地或者A点任意分身，问最少要走几步，这个人可以踩遍地图中所有的A点。思路：感觉就算读懂了题目，也比较难想到这用到了最小生成树的知识，因为可以分身，所以每个点可以向其他点都连上边。可以用bfs...
poj 3026 Borg Maze bfs建图+最小生成树
题目说从S开始，在S或者A的地方可以分裂前进。 想一想后发现就是求一颗最小生成树。首先bfs预处理得到每两点之间的距离，我的程序用map做了一个映射，将每个点的坐标映射到1-n上，这样建图比较方便。然后一遍prime就够了。注意用gets（）读入地图的时候，上面还要用一个gets（）接住无用的空格。...
poj 3026 Borg Maze (bfs + 最小生成树)
链接:poj 3026题意：y行x列的迷宫中，#代表阻隔墙（不可走）。空格代表空位（可走）。S代表搜索起点（可走）,A代表目的地（可走），如今要从S出发，每次可上下左右移动一格到可走的地方。求到达全部的A的路线总距离最小值分析：能够先用bfs从上下左右四个方向将全部的A,S两两之间的最短距离，题目的...