Leetcode 1584: Min Cost to Connect All Points

 https://leetcode.com/problems/min-cost-to-connect-all-points/description/

Notes:

[udpate 2020-09-13]

In the first method (see below), we keep a very large priority queue, which actually is not necessary. 

Here is a better way to maintain the information in the spanning process. 

1): will use a vector to label whether a node is connected or not. (index for node, value for connected condition: 1 for connected, 0 for dis-connected);

2): will use a second vector to label the shortest distance for a dis-connected node to all the connected nodes. This needs to be updated when a new node becomes connected.

But the basic idea is the same: find the node (or point) having the shortest distance to the nodes already connected.

See the code below:

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        vector<int> used(n, 0), mxs(n, INT_MAX);
        mxs[0] = 0;
        for(int i=0; i<n; ++i) {
            // find the next node with the shortest distance
            int id = 0, mm = INT_MAX;
            for(int j=0; j<n; ++j) {
                if(!used[j] && mxs[j] < mm) {
                    id = j;
                    mm = mxs[j];
                }
            }
            used[id] = 1;
            res += mm;
            // update mxs (since a new element at id is added in, so just need to update the shortest dis to it)
            for(int j=0; j<n; ++j) {
                if(used[j]) continue;// if connected already, continue
                int dis = abs(points[id][0] - points[j][0]) + abs(points[id][1] - points[j][1]);
                if(dis < mxs[j]) mxs[j] = dis;
            }
        }
        return res;
    }
};

This is question can be viewed as a variation of minimum spanning tree. In some sense, it is also similar to Dijkstra algorithm.

Since eventually we need to connect all the nodes, so it does not matter starting with which one.

Similar to Dijkstra, we will have a connected pool: set, and the distance rank: a reversed priority queue.

Let start with points[0], 

1): then we will choose the point with the shortest distance with points[0] as the next one;

so a reversed priority_queue can be used;

2): after having the second points, we need to put all the distance from the second points to the rest points into the priority_queue;

3): the top of the priority_queue should always be the next points to be connected (this is exactly the same as Dijkstra)

4): after having the next points, we should update all the available distances into the priority_queue...

until all the nodes are connected.

Since we have a set to record the connected nodes, so we just can use this to avoid duplicated visiting.

See the code below:

class Solution {
public:
    typedef pair<int, int> pi;
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        priority_queue<pi, vector<pi>, greater<pi>> pq;
        set<int> st;
        st.insert(0);
        for(int i=1; i<n; ++i) {
            int dis = abs(points[0][0] - points[i][0]) + abs(points[0][1] - points[i][1]);
            pq.push({dis, i});
        }
        while(st.size() < n) {
            while(st.count(pq.top().second)) pq.pop();
            if(pq.empty()) break;
            auto t = pq.top();
            int d = t.first, id = t.second;
            res += d;
            // cout<<res<<" "<<d<<endl;
            st.insert(id);
            for(int i=0; i<n; ++i) {
                if(st.count(i)) continue;
                int dis = abs(points[id][0] - points[i][0]) + abs(points[id][1] - points[i][1]);
                pq.push({dis, i});
            }
        }
        return res;
    }
};

Leetcode 1168: Optimize Water Distribution in a Village

https://leetcode.com/problems/optimize-water-distribution-in-a-village/description/

Notes:

This is another question about minimum spanning tree (MST). But we need to convert "digging wells" into "connections": for example, connections to well 0. Thus, it is become the same as Leetcode 1135: Connecting Cities With Minimum Cost 

The key point is it will use the standard union-find method. And the algorithm for MST is Kruskal's algorithm which is in a greedy fashion.

See the code below:

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        int res = 0;
        for(int i=1; i<=n; ++i) pipes.push_back({0, i, wells[i-1]});
        sort(pipes.begin(), pipes.end(), [](auto &a, auto &b) {return a[2] < b[2];});
        vector<int> f(n+1, 0);
        for(int i=0; i<f.size(); ++i) f[i] = i;
        int ct = 0;
        for(auto &p : pipes) {
            int a = find(f, p[0]), b = find(f, p[1]);
            if(a != b) {
                f[b] = a;
                res += p[2];
                ++ct;
                if(ct==n) break;
            }
        }
        return res;
    }
private:
    int find(vector<int> &f, int x) {
        if(f[x] != x) f[x] = find(f, f[x]);
        return f[x];
    }
};

Here is another implementation using object-oriented design model. See the code below:

class unite_find {
private:
    vector<int> rt;
public:
    unite_find(int x) { //constructor
        for(int i=0; i<x; ++i) rt.push_back(i);
    }
   
    ~unite_find() {};//destructor

    int find(int x) {
        if(rt[x] != x) rt[x] = find(rt[x]);
        return rt[x];
    }

    void unite(int x, int y) {
        rt[x] = y;
    }
};

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        int res = 0;
        for(int i=1; i<=n; ++i) pipes.push_back({0, i, wells[i-1]});
        sort(pipes.begin(), pipes.end(), [](const auto &a, const auto &b) {return a[2] < b[2];});
        unite_find uf(n+1);
        for(auto &p : pipes) {
            int a = uf.find(p[0]), b = uf.find(p[1]);
            if(a != b) {
                uf.unite(a, b);
                res += p[2];
            }
        }
        return res;
    }
};

Leetcode 1135. Connecting Cities With Minimum Cost

https://leetcode.com/problems/connecting-cities-with-minimum-cost/description/

Description:

There are N cities numbered from 1 to N.
You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together. (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)
Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1.

Notes:

This question asks for the weights of the minimum spanning tree. There are very good resource online to this topic. For example,

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

The key algorithm involved is the so called union-find algorithm, which can be find in the below link,

https://www.geeksforgeeks.org/union-find/

See the code below:

class Solution {
public:
    int minimumCost(int N, vector<vector<int>>& conections) {
        sort(conections.begin(), conections.end(), [](auto &a, auto &b){return a[2] < b[2];});
        vector<int> ps(N+1, 0);
        for(int i=1; i<=N; ++i) ps[i] = i;
        int res = 0, ct = 1;
        for(auto &a : conections) {
            int x = find(a[0], ps), y = find(a[1], ps);
            if(x != y) {
            ps[x] = y;
            res += a[2];
            ++ct;
            if(ct==N) return res;
            }
        }
        return -1;
    }
private:
    int find(int x, vector<int> &ps) {
        if(ps[x] != x) ps[x] = find(ps[x], ps);
        return ps[x];
    }
};