算法拾遗 2018.11.19

算法拾遗,找回丢失的记忆。

为了能回到高三前期的水平,先着手复习一下原来的知识吧。


碎片一 树状数组

一种时间复杂度为log级别的数据结构,支持单点维护和求区间和。树状数组可以在大数据下快速计算区间和以及维护最大值最小值。

lowbit操作:

int lowbit(int m) {
    return m&(-m);//位运算
}

求前缀区间和:

int sumele(int n){
    int sum = 0;
    while (n>0){
        sum += c[n];
        n -= lowbit(n);
    }
    return sum;
}

单点更新:

void update(int i,int val){
    while (i<=n){
        c[i] += val;
        i += lowbit(i);
    }
}

它只是一种维护的手段,实质上还是求区间和。

碎片二 并查集

本能反应是想到一个菊花型的结构。

这其实是用路径压缩形成的一种很特殊的树形结构,每棵树的根节点都是一个代表元素。

并查集初始化时,集合的每个元素都是自己是自己的代表元素,所以

for (int i=1;i<=n;i++)
    father[i] = i;

用它就可以初始化一个并查集。

合并集合很简单,把一棵树上的根节点变成另一棵树上的子结点就好。

void merge(int x,int y){
    x = find(x);
    y = find(y);
    father[y] = x;
}

并查集的路径压缩的查找祖先方法。

int find(int x){
    if (father[x] == x)
    return father[x];
    father[x] = find(father[x]);//如果当前节点的father并不是代表元素,那就递归地更新老祖宗
    return father[x];//返回老祖宗
}

判断两个元素是否在同一集合:

bool check(int x,int y){
    x = find(x);
    y = find(y);
    if (x==y)
        return true;
    else
        return false;
}

碎片三 kruskal算法

按照边权排序所有边,然后从低到高一条一条取,每次取一条边询问这条边的两个点在不在同一个集合里,如果不在同一集合说明可以进行合并(因为如果在同一集合里,再连就不是树了),然后并这两个点,这个操作一直做,做到生成树已经有n-1条边为止。

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define maxn 233333
using namespace std;

struct Edge {
    int from, to, dis;

    bool operator<(const Edge &rhs)const {
        return dis < rhs.dis;
    }
};

Edge edge[maxn];
int n, m;
int totedge = 0;
int x, y, z;

int father[maxn];

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

void merge(int x, int y) {
    father[find(x)] = find(y);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].from >> edge[i].to >> edge[i].dis;
    }
    sort(edge + 1, edge + m + 1);
    for (int i = 1; i <= n; i++)
        father[i] = i;

    int totedge = 0;
    int ans = 0;
    int k = 0;
    while (totedge < n-1) {
        if (find(edge[++k].from) != find(edge[k].to)) {
            ans += edge[k].dis;
            merge(edge[k].from, edge[k].to);
            totedge++;
        }
    }
    cout << ans << endl;
//    system("pause");
    return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。