wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

图论

图的连通性

有向图的强连通分量

无向图的割点割边和双连通分量

流和匹配

最大流

最大流的一些应用

最小割

费用流

带上下界的网络流

二分图匹配

二分图最大权匹配

网络流综合

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最小生成树

最短路

差分约束

[[ item.c ]]

最小生成树

## Boruvka 算法
Boruvka 算法实际上是多源 Prim，在处理**完全图**，边权形如$$a_i \oplus a_j$$的问题中
效率很高
![](/media/content_img/boruvka-trie-merge.png)

### Educational Codeforces Round 32
**[G. Xor-MST](https://codeforces.com/contest/888/problem/G)**
给定一个完全图，每个节点的权值是$$a_i$$，任意两条边的边权是$$w(i, j) = a_i \oplus a_j$$
求完全图的最小生成树

**算法分析**
Boruvka 算法的模版题，用`DynamicTrie`的合并和并查集即可完成
> 优化，在最小生成树中，边权既然是`xor`，那么**边权相同的边，肯定是优先相连**
并且他们的边权值是`0`，不会对结果有影响，所以先把边权相同的边合并即可
解决方法是**对`a[i]`排序后去重**（boruvka 算法是合并连通块，哪个在前哪个在后没有影响）

```bash
void solve(int cas) {
    int n;
    cin >> n;

vector<i64> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

sort(a.begin()+1, a.end());
    a.erase(unique(a.begin()+1, a.end()), a.end());
    n = a.size() - 1;

// init
    DynamicTrie tr(n);
    DSU<int> dsu(n + 5);

vector<int> trie(n+5, 0);
    for (int i = 1; i <= n; i++) {
        tr.insert(trie[0], a[i], i);
        tr.insert(trie[i], a[i], i);
    }

// Boruvka 主过程
    int CC = n;
    i64 res = 0;
    using pr = pair<i64, int>;
    
    while (CC > 1) {
        // 维护每个连通块到外部世界的最小边权, (wgt, 连到目的连通块的 id)
        // 遍历每个点并尝试更新
        vector<pr> mnedge(n + 5, {inf<i64>, 0});
        for (int i = 1; i <= n; i++) {
            int X = dsu.find(i);
            auto [wgt, ccid] = tr.query(trie[0], trie[X], a[i]);

if (ccid != 0 and mnedge[X].first > wgt) {
                mnedge[X] = {wgt, ccid};
            }
        }   
        
        // 统一合并
        bool mergeAny = false;
        for (int i = 1; i <= n; i++) {
            if (dsu.find(i) != i) continue;
            int X = i;

if (mnedge[X].second != 0) {
                auto [wgt, Y] = mnedge[X];
                Y = dsu.find(Y);

if (X == Y) continue;

dsu.merge(X, Y);
                trie[X] = tr.merge(trie[X], trie[Y]);

mergeAny = true;
                CC--, res += wgt;
            }
        }
        if (!mergeAny) break;
    }

cout << res << "\n";
}
```

## 完全图的最小生成树
**[D. 最小生成树](https://qoj.ac/contest/1875/problem/9904)**
给定`n`的完全图，每两个点$$(i, j)$$，边权给定，是$$a\_{i+j}$$，求图的最小生成树，输出生成树的边权和

**算法分析**
> 回文串 + 线段树维护正反哈希 + 启发式合并

![](/media/content_img/fullMST-01.png)
![](/media/content_img/fullMST-02.png)
![](/media/content_img/fullMST-03.png)

**算法实现**
```bash
void solve(int cas) {
    int n;
    cin >> n;
    int N = 2 * n;

vector<int> a(N+1, 0);
    for (int i = 3; i <= N - 1; i++) cin >> a[i];

using pr = pair<i64, int>;
    vector<pr> edges;
    for (int i = 3; i < N; i++) edges.emplace_back(a[i], i);
    // debug(a);

ranges::sort(edges);

Segtree<Info> tr(n);
    vector<vector<int> > S(n+5);
    DSU<int> dsu(n+5);
    
    // init
    for (int i = 1; i <= n; i++) {
        S[i].emplace_back(i);
        u64 sha = rng();
        tr.change(i, Info{sha, sha, 1});
    }

i64 res = 0;
    int cc = 0;
    for (auto [wgt, K] : edges) {
        int L = max(1, K - n);
        int R = (K - 1) / 2;

auto bsearch = [&](int l, int r) -> int {
            while (l < r) {
                int mid = (l + r) >> 1;
                auto FSHA = tr.rangeQuery(L, mid).fsha;
                auto BSHA = tr.rangeQuery(K-mid, K-L).bsha;

if (FSHA == BSHA) l = mid + 1;
                else r = mid;
            }
            return l;
        };

auto merge = [&](int p) -> void {
            int X = dsu.find(p), Y = dsu.find(K - p);
            if (X == Y) return;
            if (S[X].size() < S[Y].size()) swap(X, Y);
            // Y -> X
            u64 tarsha = tr.rangeQuery(X, X).fsha;
            
            // set, change
            for (auto x : S[Y]) {
                tr.change(x, Info{tarsha, tarsha, 1});
                S[X].emplace_back(x);
            }

S[Y].clear();
            dsu.merge(X, Y);

res += wgt, cc += 1;
        };

while (L <= R) {
            auto FSHA = tr.rangeQuery(L, R).fsha;
            auto BSHA = tr.rangeQuery(K-R, K-L).bsha;

if (FSHA == BSHA) break;

int p = bsearch(L, R);
            merge(p);

if (cc >= n - 1) break;
            L = p + 1;
        }
    }

cout << res << "\n";
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

最小生成树

目录