水资源分配优化

// Leetcode 1168: Optimize Water Distribution in a Village
// Problem: Given a number of houses and a number of wells, we need to find the minimum cost to supply water to all houses.
// Solution: This problem can be solved using Kruskal's algorithm for Minimum Spanning Tree (MST). We treat each house and well as nodes in a graph, 
// and the pipes as edges with weights corresponding to the costs. We then find the MST of this graph to get the minimum cost.

import java.util.*;
import java.util.stream.*;

class Solution {
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        // Create a list to hold all the edges (pipes and wells)
        List<int[]> edges = IntStream.range(0, wells.length)
                                    .mapToObj(i -> new int[]{0, i + 1, wells[i]})
                                    .collect(Collectors.toList());

        // Add the given pipes as edges
        edges.addAll(Arrays.asList(pipes));

        // Sort edges by cost
        edges.sort(Comparator.comparingInt(a -> a[2]));

        // Create a union-find (disjoint-set) structure
        int[] parent = IntStream.range(0, n + 1).toArray();

        // Function to find the root of a node
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        // Function to union two sets
        void union(int x, int y) {
            parent[find(x)] = find(y);
        }

        final int[] totalCost = {0};

        // Kruskal's algorithm to find MST
        edges.stream()
              .filter(edge -> find(edge[0]) != find(edge[1]))
              .forEach(edge -> {
                  union(edge[0], edge[1]);
                  totalCost[0] += edge[2];
              });

        return totalCost[0];
    }
}