day 8 生成树笔记

常规
1

生成树

prufer 序列

  • 对于一颗顶点已经经过编号的树 T ，顶点的编号为 \{1,2,...,n\} ，在第 i 步时，一曲所有叶子节点（度数为1的顶点）中标号最小的顶点和相连的边，并把与它相邻的点的编号加入 prufer 序列中，重复以上步骤直到原图仅剩 2 个顶点。
  • 一个长度为 n-2 的 prufer 序列，唯一对应一颗 n 个点固定形态的无根树
  • n 个点的有标号的无根树的方案数是 n^{n-2} 。
  • n 个点的有标号的有根树的方案数是 n^{n - 1} 。
  • 先找到编号最小的叶子节点，设其为 p 。
  • 将 p 的父节点 f 加入序列。
  • 若删去 p 结点后， f 结点变为叶子节点，且 f < p ，则此时可以立即将 f 作为新选择的叶子节点进行操作。因为 p 已经是之前最小的叶子节点， f 比其更小，所以删去 p 后 f 就变成了最小，可以略去这一步直接选择它
  • 一直执行上一步直到不满足，此时将 p 自增，直到找到下一个叶子节点
  • 时间复杂度 O(n) 。
  • 构造完后剩下的两个节点里，一定有一个是编号最大的节点
  • 在 prufer 序列中，点 u 出现的次数，等于点 u 在树中的度数 -1 。

kruskal 算法

  • 以边为基础

Prim 算法

  • 以点为基础

kruskal 重构树

  • 根据 kruskal 算法的思想
  • kruskal 重构树的叶子节点为原图中的点，其他店为虚点，点权为原图中的边权
  • 例题：P4768 [NOI2018] 归程
  • 建 kruskal 重构树，维护每个子树的根到子树内的最短路，倍增查询满足条件的最小答案

Boruvka 算法

给定 n 个点的无向完全图，每个点有一个点权为 a_i ，连接 i 号节点和 j 号节点的边的边权为 a_i \oplus a_j ，求这个图的 MST 的权值

  • 一开始把每个点视为一个连通块

  • 每次用 Trie 树找到边权最小 & 不同色的另一个连通块，染成同一个颜色

    OI Wiki

课后任务

  • 第一次测试订正到340分 [ok]

  • 完成课后练习 [ok]

    左边 n 个点，右边 m 个点，左边的点只能向右边的点连边，求生成树方案

    感觉是 (n + m - 1）* (n + m - 2) * ... * n

    左边可以连右边和左边除自己外的点，左边第二个点可以连右边和左边除自己和第 n

  • 生成树博客总结 [ok]

课后习题

电话连线

  • 裸的最小生成树模板题

    #include<bits/stdc++.h>
#define mk make_pair
using namespace std;
const int maxn = 105;
int n,mp[maxn][maxn],fa[maxn],R[maxn],tot,ans,cnt; vector<pair<int,pair<int,int> > > e;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void Onion(int x,int y) {
    x = find(x), y = find(y);
    if (x == y) return ;
    if (R[x] <= R[y]) fa[x] = y;
    else fa[y] = x;
    if (R[x] == R[y]) R[x] ++;
}
void kruskal() {
    sort(e.begin(),e.end());
    for (auto E : e) {
        int u = find(E.second.first), v = find(E.second.second), w = E.first;
        if (u == v) continue;
        Onion(u,v); ans += w, tot ++; if (w != 0) cnt ++;
        if (tot == n - 1) return ;
    }
}
int main() {
    scanf("%d",&n);
    for (int i = 1;i <= n;i ++) fa[i] = i,R[i] = 1;
    for (int i = 1; i <= n;i ++)
        for (int j = 1;j <= n;j ++) {
            scanf("%d",&mp[i][j]);
            e.push_back(mk(mp[i][j],mk(i,j)));
        }
    kruskal();
    printf("%d\n%d",cnt,ans);
    return 0;
}

过路费

  • kruskal 重构树，重构后查询边权最大值等于求重构树上两点的 lca 的权值

    #include<bits/stdc++.h>
#define mk make_pair
using namespace std;
const int maxn = 20005,maxm = 200005;
int n,m,q,fa[maxn],R[maxn],f[maxn][30],w[maxn],tot,depth[maxn]; vector<int> mp[maxn]; vector<pair<int,pair<int,int> > > e;
bool vis[maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void dfs(int x,int ff) {
    // if (vis[x]) return ;
    // cout << x << '\n';
    vis[x] = true, depth[x] = depth[ff] + 1, f[x][0] = ff;
    for (int i = 1;i < 30;i ++) f[x][i] = f[f[x][i - 1]][i - 1];
    for (auto v : mp[x]) {
        if (v == ff) continue;
        dfs(v,x);
    }
}
void addEdge(int u,int v,int w) { e.push_back(mk(w,mk(u,v))); }
void build_tree() {
    sort(e.begin(),e.end()); tot = n;
    for (auto E : e) {
        int u = find(E.second.first), v = find(E.second.second), ww = E.first;
        if (u == v) continue;
        w[++ tot] = ww; fa[u] = fa[v] = tot;
        mp[tot].push_back(v); mp[tot].push_back(u);
        mp[v].push_back(tot); mp[u].push_back(tot);
    }
}
int lca(int x,int y) {
    if (depth[x] < depth[y]) return lca(y,x);
    for (int k = 29;k >= 0;k --)
        if (depth[f[x][k]] >= depth[y])
            x = f[x][k];
    if (x == y) return w[x];
    for (int k = 29;k >= 0;k --)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return w[f[x][0]];
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= (n << 1);i ++) fa[i] = i;
    for (int i = 1,u,v,w;i <= m;i ++) {
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
    }
    build_tree();
    for (int i = tot;i >= 1;i --)
        if (!vis[i])
            dfs(i,0);
    scanf("%d",&q);
    for (int i = 1,u,v;i <= q;i ++) {
        scanf("%d%d",&u,&v);
        printf("%d\n",lca(u,v));
    }
    return 0;
}

新的开始

  • 可以把造发电找转化为向“总电站”（0号点）连一条代价为 v 的边

  • 转化为朴素最小生成树

    #include<bits/stdc++.h>
#define mk make_pair
using namespace std;
const int maxn = 305;
int n,fa[maxn],R[maxn],ans; vector<pair<int,pair<int,int> > > e;
void addEdge(int u,int v,int w) { e.push_back(mk(w,mk(u,v))); }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void Onion(int x,int y) {
    x = find(x), y = find(y);
    if (x == y) return ;
    if (R[x] <= R[y]) fa[x] = y;
    else fa[y] = x;
    if (R[x] == R[y]) R[x] ++;
}
void kruskal() {
    sort(e.begin(),e.end());
    for (auto E : e) {
        int u = find(E.second.first), v = find(E.second.second), w = E.first;
        if (u == v) continue;
        Onion(u,v); ans += w;
    }
}
int main() {
    scanf("%d",&n);
    for (int i = 0;i <= n;i ++) fa[i] = i;
    for (int i = 1,w;i <= n;i ++) {
        scanf("%d",&w);
        addEdge(0,i,w);
    }
    for (int i = 1;i <= n;i ++)
        for (int j = 1,w;j <= n;j ++) {
            scanf("%d",&w);
            if (i >= j) continue;
            addEdge(i,j,w);
        }
    kruskal();
    printf("%d",ans);
    return 0;
}

归程

  • 洛谷原题链接：P4768 [NOI2018] 归程

  • 先用最短路把 1 号点到其他点的最短路预处理出来，按照海拔高度从大到小排序，建 kruskal 重构树，维护重构树上每棵子树到该子树的树根的最小值，查询时倍增

    #include<bits/stdc++.h>
#define mk make_pair
using namespace std;
const int maxn = 8e5 + 5;
int T,n,m,q,k,s,cnt,dis[maxn],fa[maxn],head[maxn],R[maxn],tot,dep[maxn],h[maxn],f[maxn][30]; bool vis[maxn];
bool cmp(const pair<pair<int,int>,pair<int,int> > &x,const pair<pair<int,int>,pair<int,int> > &y) { return x.first.first > y.first.first; }
struct hyf { int a,l; } t[maxn]; struct Hyf{ int v,nxt; } tr[maxn];
vector<pair<pair<int,int>,pair<int,int> > > e; vector<pair<int,int> > mp[maxn];
void addEdge(int u,int v,int l,int a) { 
    e.push_back(mk(mk(a,l),mk(u,v))); 
    mp[u].push_back(mk(v,l)); mp[v].push_back(mk(u,l));
}
void addTreeEdge(int u,int v) {
    tr[++ cnt].v = v;
    tr[cnt].nxt = head[u];
    head[u] = cnt;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void Dijstra() {
    memset(dis,0x3f,sizeof(dis));
    dis[1] = 0; priority_queue<pair<int,int> ,vector<pair<int,int> > ,greater<pair<int,int> > > q; q.push(mk(0,1));
    while (!q.empty()) {
        pair<int,int> top = q.top(); q.pop();
        int u = top.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (auto v : mp[u])
            if (dis[v.first] > dis[u] + v.second) {
                dis[v.first] = dis[u] + v.second;
                q.push(mk(dis[v.first],v.first));
            }
    }
    for (int i = 1;i <= n;i ++) t[i].l = dis[i];  // cout << dis[i] << ' '; }
    // putchar('\n');
}
void kruskal() {
    sort(e.begin(),e.end(),cmp); tot = n;
    for (int i = 1;i <= (n << 1);i ++) fa[i] = i;
    for (auto E : e) {
        int u = find(E.second.first), v = find(E.second.second), a = E.first.first, l = E.first.second;
        if (u == v) continue;
        // // cout << u << ' ' << v << '\n'; 
        tot ++;
        addTreeEdge(tot,u); addTreeEdge(tot,v);
        // tr[u].push_back(tot); tr[v].push_back(tot);
        fa[u] = tot, fa[v] = tot; t[tot].a = a;
    }
}
void dfs(int u,int fa) {
    // cout << u << ' ' << fa << endl;
    dep[u] = dep[fa] + 1, f[u][0] = fa;
    for (int i = 1;i < 20;i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = head[u];i;i = tr[i].nxt) {
        // // cout << v << endl; 
        int v = tr[i].v; // cout << i << '\n';
        dfs(v,u);
        t[u].l = min(t[u].l,t[v].l);
    }
    // cout << u << ':' << t[u].l << '\n';
}
int query(int x,int y) {
    for (int i = 19;i >= 0;i --)
        if (dep[x] - (1 << i) > 0 && t[f[x][i]].a > y) 
            x = f[x][i];
    return t[x].l;
}
int main() {
    scanf("%d",&T);
    while (T --) {
        scanf("%d%d",&n,&m);
        for (int i = n + 1;i <= (n << 1);i ++) t[i].l = 0x3f3f3f3f;
        memset(f,0,sizeof(f)); memset(vis,0,sizeof(vis));
        for (int i = 1,u,v,l,a;i <= m;i ++) {
            scanf("%d%d%d%d",&u,&v,&l,&a);
            addEdge(u,v,l,a);
        }
        Dijstra(); kruskal();
        dfs(tot,0); 
        scanf("%d%d%d",&q,&k,&s);
        for (int i = 1,ans = 0,u,v;i <= q;i ++) {
            scanf("%d%d",&u,&v);
            u = (k * ans + u - 1) % n + 1, v = (k * ans + v) % (s + 1);
            ans = query(u,v); printf("%d\n",ans);
        }
        for (int i = 1;i <= n;i ++) mp[i].clear();
        e.clear(); memset(head,0,sizeof(head)); cnt = 0;
    }
    return 0;
}
4 个赞