狗家 建水井
https://www.1point3acres.com/bbs/thread-505957-1-1.html
第一轮建水井，一个村庄里有很多房子，有的房子旁边能建水井，有的房子只能通过与其他房子建立管道获得供水。给出了在不同房子旁边建水井的花费，已及两个房子间建管道的花费，要求结果给出一份竞价，使得总花费尽可能少 第一题就卡住了，给出了个不算特别好的算法，我又试了别的想法，但是没想出来，面试官问是要个提示还是就之前我给出的完整的算法写，我选择要了提示，面试官根据我第二个思路引导我构成联通图 最后怕时间不够写代码，提醒说用最小生成树-b
这题一周内已经看到两三次了。仔细想了一下，觉得比最小生成树更复杂，因为可以仅仅找多个联通分量，每个联通分量内只需要一个水井，最后代价最小就行，并不是一定要连通图。
感觉不要去考虑连通分量连通图之类的，直接用最小生成树的思路比较好。因为能建水井的房子，相当于有一条管道可以通往水源，管道长度就是建井费用，最后就是要用最小生成树把所有房子+水源都连接起来。
写了一个最小生成树的代码，核心思想就是维护一个PriorityQueue，每次poll出来[cost, v1, v2] 其中v1是已访问的节点，如果v2没有访问就加入到已访问节点中，然后把v2的相连的节点加到queue中。时间复杂度：用邻接表 O( VElogE)， 用邻接矩阵是O(VVlogE)
这是Lazy implementation版的Prim's algorithm
所以是O(E log E)
先建一个dummy，自己家挖水井，当成是这个房子到dummy的一个边，cost就是这个房子自己挖水井的cost，这个时候整个就是一个全连接的图，每个点和其他点都有连接，都有cost，把所有的边加到minheap中，pop cost最小的边，用union find check当前的边可以保留吗？我们的目标是pop出的边能包括所有的房子和dummy，并且没有边（使得房子有重复，会增加cost不是我们想要的） ，每pop一个边，check是不是已经find了？是，不要，不是，留下，一直到这些边包括所有的房子和dummy
https://www.1point3acres.com/bbs/thread-505957-1-1.html
第一轮建水井，一个村庄里有很多房子，有的房子旁边能建水井，有的房子只能通过与其他房子建立管道获得供水。给出了在不同房子旁边建水井的花费，已及两个房子间建管道的花费，要求结果给出一份竞价，使得总花费尽可能少 第一题就卡住了，给出了个不算特别好的算法，我又试了别的想法，但是没想出来，面试官问是要个提示还是就之前我给出的完整的算法写，我选择要了提示，面试官根据我第二个思路引导我构成联通图 最后怕时间不够写代码，提醒说用最小生成树-b
这题一周内已经看到两三次了。仔细想了一下，觉得比最小生成树更复杂，因为可以仅仅找多个联通分量，每个联通分量内只需要一个水井，最后代价最小就行，并不是一定要连通图。
感觉不要去考虑连通分量连通图之类的，直接用最小生成树的思路比较好。因为能建水井的房子，相当于有一条管道可以通往水源，管道长度就是建井费用，最后就是要用最小生成树把所有房子+水源都连接起来。
+1 所以事实上就是构建这样一个graph G=<V, E>, V包括了所有的房子+一个虚拟的水源节点，E包括了所有的管道和打井消耗，然后寻找G的MST即可
考虑到了呀。不要去想水井，就想整个村子只有一个水源，然后只有几个房子可以连到水源。最终要所有房子都有水。
你说的这个情况，那个最后的房子会直接连到水源。但无论如何，都是用一颗树把所有房子还有水源都连起来。
这是Lazy implementation版的Prim's algorithm
所以是O(E log E)
先建一个dummy，自己家挖水井，当成是这个房子到dummy的一个边，cost就是这个房子自己挖水井的cost，这个时候整个就是一个全连接的图，每个点和其他点都有连接，都有cost，把所有的边加到minheap中，pop cost最小的边，用union find check当前的边可以保留吗？我们的目标是pop出的边能包括所有的房子和dummy，并且没有边（使得房子有重复，会增加cost不是我们想要的） ，每pop一个边，check是不是已经find了？是，不要，不是，留下，一直到这些边包括所有的房子和dummy
