算法提高 Island Hopping
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
太平洋岛网公司（PLN）已经瞄向了太平洋中的一些群岛。这些群岛没有快捷的互联网连接。PLN计划向群岛提供互联网服务，以开发这个太平洋中潜在的市场。每组群岛的核心岛屿已经被深海电缆连入互联网。接下来需要做的事把其余岛屿和核心岛屿连接起来。
对于每个岛，将给出它的路由器的位置和居民数量。PIN将会在群岛中连接多条电缆，每条电缆连接两座岛的路由器，最后使得每座岛都通过一条电缆路径与核心岛屿相连。PIN希望总的电缆长度最小。这样也许会有多个最佳方案。PIN并不关心哪个最佳网络方案被采纳。
PIN对于新顾客连上互联网的平均时间很感兴趣，我们不妨假设：所有连接网络的电线都是同时开始建设的。电缆铺设效率为一千米每天。因此，短的电缆会比长的更快铺好。
当一座岛到核心岛屿的电缆连通时，这座岛就接入了互联网。PIN希望你告诉他所有居民连入互联网的平均时间。
输入格式
输入数据包含多组群岛的描述。每组描述的第一行是一个正整数n，表示群岛的数量(n ≤ 50)。接下来n行每行包含三个整数xi,yi,mi，表示路由器的位置（xi,yi），以及岛上居民数量mi (mi > 0)。坐标以千米为单位。序列中的第一座岛是核心岛屿。
输入数据最后以一个整数0结束。
输出格式
对于测试点中的每组群岛，输出该组的序列号和居民连入互联网的平均天数。保留两位小数。具体 格式如样例输出所示。
每一个测试点输出后打印一个空行。
样例输入
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0
样例输出
Island Group: 1 Average 3.20
数据规模和约定
输入数据中所有数字保证不超过2^31-1
PS.个人感觉题目有歧义，如果岛a离核心岛距离为2.5km，那么是第三天就可以连通，还是2.5天呢。答案是后者，我一开始是向上取整算的，半天都没对。
解题思路：
1.问题描述里说要电缆长度最短，首先我们要求连通n个岛屿的最短路径，自然而然地想到最小生成树，有Prim算法和Kruskal算法，前者适用于稠密图，是对点的贪心；后者适用于稀疏图，是对边贪心。本题的边有n*(n+1)/2 条，都是完全图了，所以选择Prim算法求最小生成树。而且用Prim算法还有一个好处，我们可以选择从核心岛屿开始构建树，这样得到的边的顺序也是从核心岛屿向外辐射的，这便于求各个岛屿的通网时间（如果用Kruskal算法，那么得到的边是零星的），因为子节点通网时间依赖于父节点通网时间。
2.如何得到各个岛屿的通网时间呢？首先，明确铺设电缆是同时的，各个岛屿都可以同时铺设电缆，如果各个岛屿的距离都相同，为a，那么除核心岛屿在时间为0的时候通网外，其余岛屿都是在a/1 = a时间通网（铺设电缆的速度是1km-1，电缆长度单位是km）。如果我们知道各个岛的前一个岛是什么就好了，换句话说，知道各个结点的父结点就好了，因为如果结点到父结点的时间大于父节点通网的时间，那这个结点的通网时间就是其铺设电缆到父结点的时间；若结点到父节点的时间小于其父节点通网的时间，那么其通网时间就是父节点通网的时间（如果不理解，把结点换成岛屿，父节点理解为这个岛屿往核心岛屿方向的前一个岛屿）。
3.居民连入互联网的平均天数就是一个加权的天数，可以这样算，初始平均时间ave=0，然后对每一个岛屿，都用 ave + =岛通网的天数×岛的人数/总人数。
AC代码如下
//蓝桥 算法提高 ADV-282 Island Hopping
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;const int MAXN = 50 + 1;
struct island {
int x; //位置 int y;int mi; //人数double ready; //通网的时间
}islands[MAXN];typedef struct Edge {
int from;int to;double dis; //建造路的花费 Edge(int A, int B, double Dis) {
from = A; to = B; dis = Dis; };
}edge;struct cmp {
bool operator()(edge x, edge y){
return x.dis > y.dis; //小的优先级高 ,从小到大排 }
};bool vis[MAXN];
vector<edge> S; //存放最小生成树的边
priority_queue<edge, vector<edge>, cmp> Q; //按照edge.dis升序排列，存放许多边int main() {
int n; //群岛数量double ave; //用户平均通网时间int total; //用户总人数int k = 0; //统计第几个岛群while (1) {
S.clear();while (!Q.empty()){
Q.pop();}memset(vis, 0, sizeof(vis));memset(islands, 0, sizeof(islands)); //完成初始化k++;ave = 0; total = 0; scanf("%d", &n);if (n == 0)break;for (int i = 0; i < n; i++) {
scanf("%d%d%d", &islands[i].x, &islands[i].y, &islands[i].mi);total += islands[i].mi;}vis[0] = 1; //从中心岛屿开始 prim 算法 for (int i = 1; i < n; i++) //先把以核心岛屿开始的边入队Q.push(edge(0, i, sqrt(pow(islands[0].x - islands[i].x, 2)+ pow(islands[0].y - islands[i].y, 2))));while (!Q.empty() && S.size() != n - 1) {
//当S中有n-1个元素时，n个岛屿就连通了，如果再多一条边，必定产生环，就不是树了edge now = Q.top(); //每次取出Q中最短的边Q.pop();if (vis[now.to]) //已经访问过了continue;S.push_back(now); //存到S中vis[now.to] = 1;for (int i = 1; i < n; i++) {
if (!vis[i]) {
Q.push(edge(now.to, i, sqrt(pow(islands[now.to].x - islands[i].x, 2)+ pow(islands[now.to].y - islands[i].y, 2))));}}}//求通网的时间islands[0].ready = 0; //第一个岛屿在时刻0通网for (int i = 0; i < S.size(); i++) {
edge now = S[i];if (now.dis < islands[now.from].ready) //前一个岛屿没通网 islands[now.to].ready = islands[now.from].ready;elseislands[now.to].ready = now.dis;}for (int i = 1; i < n; i++)ave += islands[i].ready/ total*islands[i].mi ; //先除再乘，防止溢出printf("Island Group: %d Average %.2f\n\n", k, ave);}return 0;
}
注意：85行开始求各个岛屿的通网时间，我们可以那样做，是因为，S中各条边from到to的方向，都是从核心岛屿往外扩散的方向，因此能保证在遍历每条边的时候，from岛屿的通网时间已经确定了，这样就可以分情况求to岛屿的通网时间了。
使用优先队列配合Prim算法更快，不用每次遍历取最短的边。优先队列格式如下：
priority_queue<int,vector<int>,greater<int> > Q; //升序排列
如果要使用自定义结构的优先队列，要写仿函数：
struct cmp {
bool operator()(edge x, edge y){
return x.dis > y.dis; //按距离升序排列}
};
priority_queue<edge, vector<edge>, cmp> Q;