POJ1287Networkoing 输入有重边的MST裸题记得判有效边PO1789Truck History 不太明显每个字符串是一个结点不同的字符数目是权重构建的是完全图最后输出1/权重和。POJ2031Building a Space Station 在构建图的权值的时候预处理。 要判断两个球体是否有接触有接触的权值为0无接触的权值为球心距离减去半径和最后构建MST。POJ1251Jungle Roads 裸题。POJ1751 Highways 裸题。POJ 2253 Frogger有一点变形当结点1、2在同一集合的之后直接break结果即当前合并边的权因为最小生成树将边集按照权值排序所以最后的加入的边权值一定最大满足题意使最大跳跃范围最小。【此题最短路径也可解】POJ 1258 Agri-Net建立一个网络使村民互联的最小耗费裸题给权重的方式是矩阵输入。POJ 2349 Arctic Network题意有S颗卫星和P个哨所有卫星的两个哨所之间可以任意通信否则一个哨所只能和距离它小于等于D的哨所通信。给出卫星的数量和P个哨所的坐标求D的最小值。MST的每一个结点都是一个集合让卫星代替最大边通信求得的D最小也就是说如果有S个卫星那么我们要求的D就是第S大的边。【想清楚这一点还是不太容易的】
