题目大意：
水资源分配优化
村庄内有n户人家，我们可以通过挖井或者建造水管向每家供水。
对于每户人家i，我们可以通过花费 wells[i] 直接在其房内挖水井，或者通过水管连接到其他的水井。每两户住户间铺设水管的费用通过 pipes 数组表示。 pipes[i] = [house1, house2, cost] 表示住户1到住户2间铺设水管的费用为cost。
请求出所有住户都能通水的最小花费。
示例1：
输入: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] 输出: 3 解释: The image shows the costs of connecting houses using pipes. The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.
提示：
1 <= n <= 10000wells.length == n0 <= wells[i] <= 10^51 <= pipes.length <= 100001 <= pipes[i][0], pipes[i][1] <= n0 <= pipes[i][2] <= 10^5pipes[i][0] != pipes[i][1]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1168
解题思路分析：
这道题出的很巧妙。我开始想使用动态规划来做，但没想到思路。看了提示才发现原来是Union-Find并查集问题。
我们将所有住户想象成n个节点，如果能将n个节点都连接起来，并且保证至少一家挖了水井，就可使得所有住户都有水喝。不过题目要求找到最优连接方案，也就是要知道如何连接节点，以及挖几口井的总花费最少。我们先来想第一个问题，比如住户A通过某条水管路线通上了水，住户B也通过某条水管通上了水，那么A和B之间是不需要再进行连线的，否则会花费多余的费用。这样一来，所有连线就不会产生回路，也就是说，最终将所有节点接起来之后，应该是一个树形结构。不过问题来了，题目给出的pipes 数组貌似并不足以让所有节点都能保证联通，也就是说，最后可能会形成多棵树，每棵树的顶点是挖井的住户。那么，这多棵树有没有同一个根节点呢？
答案是有！我们忽略了另外一个节点，即水源。本题，我们可以将水源看做是树的根节点，水源到每一个住户的花费为题目给出的 wells数组。wells 数组的长度为n，即每一家理论上都可以联通到水源。因此通过题目给出的条件我们可以得到以下数量的连线：
int lineCount = wells.length + pipes.length;
通过以上的这些条连线一定可以将所有节点以树形结构连接起来，接下来问题就转化为通过已知节点间cost，如果构建一棵总cost最小的树。
我们将所有连线按照cost由小到大排序，然后循环遍历每一条连线，如果连线上两点已经存在相同的根节点，为了避免回路，他们之间不需要连接。反之，两点间需要连接，并将连接cost加入返回结果。直到循环结束算出总cost即是返回结果。因为数组已经排序过，所以可以保证结果为最优。
最后，判断是否具有相同的根节点，只需要利用Union-find并查集即可。
实现代码：
int[] root;
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
root=new int[n+1]; // 并查集数组
for(int i=0;i<n+1;i++) root[i]=i; // 初始时每个节点的根节点为自己
// 存储所有的边
int[][] allPipes = new int[pipes.length+wells.length][3];
// 将每户与水源的连线加入allPipes数组
for(int i=0;i<n;i++){
allPipes[i]=new int[]{0, i+1, wells[i]};
}
// 将每户间的连线加入allPipes数组
for(int i=n;i<allPipes.length;i++){
allPipes[i]=pipes[i-n];
}
// 按照cost升序排序
Arrays.sort(allPipes,(x,y)->x[2]-y[2]);
int res=0; // 返回结果
for(int[] p : allPipes){
int r0=root(p[0]); // 连线上第一个节点的根节点
int r1=root(p[1]); // 连线上第二个节点的根节点
if(r0==r1) continue; // 根节点相同，不需此连线
// 以下均为不在同一根节点下的情况
// 某一个点的根节点为水源
if(r0==0 || r1==0){
// 将另一节点也加到根节点下（Union合并操作）
root[r0]=0;
root[r1]=0;
} else{
// 将一个根节点加入到另一个根节点下（Union合并操作）
root[r1]=r0;
}
res+=p[2]; // 将当前连线cost加入返回结果
}
return res;
}
int root(int i){ // 查找根节点
while(root[i]!=i) i=root[i];
return i;
} 本题解法执行时间为29ms。
Runtime: 29 ms, faster than 87.65% of Java online submissions for Optimize Water Distribution in a Village.
Memory Usage: 55.8 MB, less than 100.00% of Java online submissions for Optimize Water Distribution in a Village.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1168-optimize-water-distribution-in-a-village-解题思路分析/