论 Fibonacci 堆的常数到底有多少

cancan123456 @ 2022-10-15 09:42:09

by cancan123456 @ 2022-10-15 09:42:28

代码：

#include <cstdio>
#include <vector>
using namespace std;
const int N = 100000;
void print_heap(int n);
struct KeyValue {
    int u, dis;
    KeyValue() {
    }
    KeyValue(int u_, int dis_) {
        u = u_;
        dis = dis_;
    }
};
bool operator < (const KeyValue & a, const KeyValue & b) {
    return a.dis < b.dis;
}
struct FibonacciHeapNode {
    KeyValue key;
    FibonacciHeapNode * child, * left, * right, * father;
    int degree;
    bool mark;
    FibonacciHeapNode(KeyValue x) {
        key = x;
        child = left = right = father = nullptr;
        degree = 0;
        mark = false;
    }
    void insert(FibonacciHeapNode * p) {
        p -> left = left;
        p -> right = this;
        left -> right = p;
        left = p;
    }
    void remove() {
        right -> left = left;
        left -> right = right;
        left = right = this;
    }
    void cut() {
        father -> degree--;
        if (left == this) {
            father -> child = nullptr;
        } else {
            if (father -> child == this) {
                father -> child = left;
            }
            remove();
        }
        father = nullptr;
    }
};
int log2(int x) {
    for (int i = 0; ; i++) {
        if (x < (1 << i)) {
            return i - 1;
        }
    }
}
void swap(FibonacciHeapNode * & a, FibonacciHeapNode * & b) {
    FibonacciHeapNode * temp = a;
    a = b;
    b = temp;
}
struct FibonacciHeap {
    FibonacciHeapNode * min, ** cons;
    int node_number;
    FibonacciHeap() {
        min = nullptr;
    }
    FibonacciHeapNode * insert(KeyValue key) {
        FibonacciHeapNode * p = new FibonacciHeapNode(key);
        if (min == nullptr) {
            min = p;
            min -> left = min -> right = min;
        } else {
            min -> insert(p);
            if (p -> key < min -> key) {
                min = p;
            }
        }
        node_number++;
        return p;
    }
    void merge(FibonacciHeap * other) {
        min -> left -> right = other -> min;
        other -> min -> left -> right = min;
        swap(min -> left, other -> min -> left);
        if (other -> min -> key < min -> key) {
            min = other -> min;
        }
        other -> min = nullptr;
        node_number += other -> node_number;
    }
    KeyValue find_min() {
        return min -> key;
    }
    void consolidate() {
        int length = log2(node_number) + 2;
        cons = new FibonacciHeapNode * [length];
        for (int i = 0; i < length; i++) {
            cons[i] = nullptr;
        }
        while (min != nullptr) {
            FibonacciHeapNode * p = min;
            if (min -> left != min) {
                min = min -> right;
                p -> remove();
            } else {
                min = nullptr;
            }
            if (cons[p -> degree] == nullptr) {
                cons[p -> degree] = p;
            } else {
                if (p -> key < cons[p -> degree] -> key) {
                    swap(cons[p -> degree], p);
                }
                if (cons[p -> degree] -> child == nullptr) {
                    cons[p -> degree] -> child = p;
                } else {
                    cons[p -> degree] -> child -> insert(p);
                }
                cons[p -> degree] -> degree++;
                p -> father = cons[p -> degree];
                int now = p -> degree;
                while (cons[now + 1] != nullptr) {
                    if (cons[now] -> key < cons[now + 1] -> key) {
                        swap(cons[now], cons[now + 1]);
                    }
                    cons[now + 1] -> child -> insert(cons[now]);
                    cons[now + 1] -> degree++;
                    cons[now] -> father = cons[now + 1];
                    cons[now] = nullptr;
                    now++;
                }
                cons[now + 1] = cons[now];
                cons[now] = nullptr;
            }
        }
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (cons[i] != nullptr) {
                cons[count] = cons[i];
                count++;
            }
        }
        for (int i = 0; i < count; i++) {
            cons[i] -> left = cons[(i - 1 + count) % count];
            cons[i] -> right = cons[(i + 1) % count];
        }
        min = cons[0];
        for (int i = 1; i < count; i++) {
            if (cons[i] -> key < min -> key) {
                min = cons[i];
            }
        }
        delete [] cons;
    }
    void extract_min() {
        if (min -> child != nullptr) {
            while (min -> child != nullptr) {
                FibonacciHeapNode * p = min -> child;
                p -> cut();
                min -> insert(p);
            }
        }
        if (node_number == 1) {
            min = nullptr;
        } else {
            FibonacciHeapNode * p = min -> right;
            min -> remove();
            delete min;
            min = p;
        }
        node_number--;
        if (node_number >= 1) {
            consolidate();
        }
    }
    void cascading_cut(FibonacciHeapNode * p) {
        if (p -> father != nullptr) {
            if (p -> mark) {
                cascading_cut(p -> father);
                p -> cut();
                min -> insert(p);
                p -> father = nullptr;
                p -> mark = false;
            } else {
                p -> mark = true;
            }
        }
    }
    void decrease_key(FibonacciHeapNode * p, KeyValue new_key) {
        if (p -> key < new_key) {
            printf("Error The new key is greater than current key.\n");
            return;
        }
        p -> key = new_key;
        if (p -> father != nullptr && new_key < p -> father -> key) {
            cascading_cut(p -> father);
            p -> cut();
            min -> insert(p);
            p -> mark = false;
        }
        if (p -> key < min -> key) {
            min = p;
        }
    }
    void delete_node(FibonacciHeapNode * p) {
        decrease_key(p, KeyValue(p -> key.u, -2147483647 - 1));
        extract_min();
    }
};
struct Edge {
    int v, w;
    Edge() {
    }
    Edge(int v_, int w_) {
        v = v_;
        w = w_;
    }
};
vector < Edge > edge[N];
int dis[N];
FibonacciHeapNode * node[N];
FibonacciHeap heap;
int main() {
    int n, m;
    scanf("%d %d %*d", &n, &m);
    for (int u, v, w, i = 1; i <= m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        u--;
        v--;
        edge[u].push_back(Edge(v, w));
    }
    for (int u = 0; u < n; u++) {
        dis[u] = 0x3f3f3f3f;
    }
    dis[0] = 0;
    for (int i = 0; i < n; i++) {
        node[i] = heap.insert(KeyValue(i, dis[i]));
    }
    for (int u, i = 0; i < n; i++) {
        u = heap.find_min().u;
        node[u] = nullptr;
        heap.extract_min();
        for (Edge to : edge[u]) {
            if (dis[to.v] > dis[u] + to.w) {
                dis[to.v] = dis[u] + to.w;
                heap.decrease_key(node[to.v], KeyValue(to.v, dis[to.v]));
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", dis[i]);
    }
    return 0;
}

by wangzikang @ 2022-10-15 09:50:51

zgc 爆切Fib堆%%%%%%

建议学习一下这个

by sunrise1024 @ 2022-10-15 09:55:06

@cancan123456 这里n和m差距不大，常数大点就慢了，要试这个代码的效率的话建议跑完全图

by 鏡音リン @ 2022-10-15 10:12:02

@sunrise1024 完全图谁拿堆跑dijkstra啊？

by cancan123456 @ 2022-10-15 10:44:03

@sunrise1024 完全图直接暴力都比堆快。

by cancan123456 @ 2022-10-15 10:44:45

要不造个 1e6 级别的图跑跑？

by cancan123456 @ 2022-10-15 10:49:16

by cancan123456 @ 2022-10-15 11:28:20

by bai_tang @ 2022-10-15 11:57:38