DAY15 - 最小生成树

今天写最小生成树~~
会提到的相关内容：

1. BFS
2. 堆结构
3. 并查集
4. 贪心
   直接放个例题来说明

例题&算法

1135. 最低成本联通所有城市
题目叙述：给一张图(有权值)，权值代表连接两点所需要的成本，返回连接所有点的最小成本，如果无法连接，则返回-1

[法一]Prim 贪心

思路：

1. 从哪开始，答案会是一样的->随意选一个起点
2. 用priority_queue(堆)实现贪心思想(利用pq来搜索路径)
   ((取出pq最前面的元素，放入相邻的节点))
   这个实现与理解上应该都很容易，问题是证明吧(?

WHY?

贪心法虽然好理解也好实作，可是证明却没有那麽的直观
贪心法一直在找权值最小的边，所以可以做这样的假设
1.若一个权值最小的边不在最小生成树里面
2.把这条边加入那个不含权值最小的边的最小生成树
3.这时候会形成环
4.去除一条权值较大的边(一定有，因为加入的边是权值的)
5.形成更小的生成树
以此发现，要选择权值最小的边
最後是程序码实现~~

#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
#define mp make_pair
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        //转换成点->(点, 权重)
        vt<vt<iipair>> edges(n+1);
        for(auto con:connections){
            edges[con[0]].pb(mp(con[1], con[2]));
            edges[con[1]].pb(mp(con[0], con[2]));
        }
        priority_queue<iipair, vector<iipair>, greater<iipair> > pq;
        pq.push(mp(0, 1)); //greater<iipair>会比较pair.first
        //(cost, i)
        vt<int> vis(n+1, 0);
        int res = 0;
        int cnt = 0;
        while(!pq.empty()){
            auto top = pq.top();
            pq.pop();
            int i = top.second;
            int cost = top.first;
            if(vis[i]){
                continue;
            }
            vis[i] = 1;
            res+=cost;
            cnt++;
            for(auto edge:edges[i]){
                int next_i = edge.first;
                int next_cost = edge.second;
                if(!vis[next_i]){
                    pq.push(mp(next_cost, next_i));
                }
            }
        }
        if(cnt==n){
            return res;
        }
        return -1;
    }
};

[法二]Kruskal 并查集+贪心

思路：
1.对边依权值排序
2.从权值小的边开始连接
3.如果两点未被连接过，就计算权重
4.利用并查集将连接的点并起来~~
直接放程序码~~

class dsu{
public:
    int arr[10005];
    dsu(){
        for(int i = 0; i<10005; ++i){
            arr[i] = i;
        }
    }
    int find(int i){
        if(arr[i]==i){
            return i;
        }
        return arr[i] = find(arr[i]);
    }
    void merge(int a, int b,int w, int& cnt, int& res){ //把b并进a
        int a_head = find(a);
        int b_head = find(b);
        if(a_head!=b_head){
            cnt++;
            arr[b_head] = a_head;
            res+=w;
        }
    }
};
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        /*
        Kruskal
        1. sort edges
        2. dsu merge
        */
        if(connections.size()<n-1){
            return -1;
        }
        auto cmp = [] (vector<int> a, vector<int> b){
            return b[2]>a[2];
        };
        dsu ddsu;
        sort(connections.begin(), connections.end(), cmp);
        int res = 0;
        int cnt = 0;
        for(int i = 0; i<connections.size()&&cnt<n-1; ++i){
            ddsu.merge(connections[i][0], connections[i][1], connections[i][2], cnt, res);
        }
        return res;
    }
};

Union权值优化

这个名字其实我不太确定(?
反正就是给并查集一个大小的权值，只把小的往大的并

class dsu{
private:
    vector<int> arr;
    vector<int> ssize;
public:
    dsu(int n){
        arr.resize(n+1);
        ssize.resize(n+1);
        for(int i = 1; i<n+1; ++i){
            arr[i] = i;
            ssize[i] = 1;
        }
    }
    int find(int i){
        if(arr[i]==i){
            return i;
        }
        return find(arr[i]);
    }
    void merge(int a, int b,int w, int& cnt, int& res){ //把b并进a
        int a_head = find(a);
        int b_head = find(b);
        if(a_head!=b_head){
            if(ssize[a_head]>ssize[b_head]){//a较大
                arr[b_head] = a_head; //b并进a
                ssize[a_head]+=ssize[b_head];
            }
            else{
                arr[a_head] = b_head;
                ssize[b_head]+=ssize[a_head];
            }
            //arr[b_head] = a_head;
            res+=w;
            cnt++;
        }
    }
};
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        /*
        Kruskal
        1. sort edges
        2. dsu merge
        */
        int m = connections.size();
        if(m<n-1){
            return -1;
        }
        auto cmp = [] (vector<int>& a, vector<int>& b){
            return b[2]>a[2];
        };
        sort(connections.begin(), connections.end(), cmp);
        int res = 0;
        int cnt = 0;
        dsu ddsu(n);
        for(int i = 0; i<m&&cnt<n-1; ++i){
            ddsu.merge(connections[i][0], connections[i][1], connections[i][2], cnt, res);
        }
        return res;
    }
};