[笔记]Kruskal重构树

I_am_konjac · 2023-08-24 19:30:44 · 个人记录

Kruskal重构树

首先我们需要学习的是Kruskal最小生成树

概念：

在一张无向图中，对最小生成树构建一颗新的树，使得同时具有边权的单调性又保持子图的联通性。

使用场景：

在无向图中找两个节点x和y的路径上的最大边权或最小边权；
在无向图中，限制移动的大小，找到可以连通的点数；

构建步骤：

将无向图的边按照权值排序；
枚举排序后的边e_i将2个端点x_i和y_i所在的两颗树的根节点合并，并新建节点cnt，左右子节点分别为x_i,y_i的根节点，将e_i的边权w_i设为节点cnt的点权。
若x_i和y_i已经在一棵树中，则跳过e_i;
重复步骤2-3,直到无向图的所有节点连成一颗新的树。

建成的这棵极具迷惑性的树就是我们的Kruskal重构树，我们构建一棵这样的树只需要O(M log_M )的时间复杂度，非常的银杏化。

性质：

树上所有叶子节点都是原图中的节点;
新建的节点共n-1个，总结点共2n-1个;
整棵树非叶子节点且点权从根节点到叶子节点具有单调性;
Kruskal重构树的任意一棵子树，在原图中一定联通且不依赖于子树外的节点；

板子题：

P1967 [NOIP2013 提高组] 货车运输

构建一棵Kruskal重构树，然后对于询问x和y， x,y的lca就是答案

注：basket # 1中增加了hack数据点，并不保证询问的x和y联通，所以需要特判

因为本人马蜂过于抽象，所以直接上@apple365带注释的优美代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500005;
int n, m, s, cnt, point;
int head[maxn], d[maxn], dp[maxn][21], lg[maxn], fa[maxn], val[maxn]; //d深度， dp记祖先是谁 
bool vis[maxn];
struct node
{
    int to, next;
}e[2 * maxn]; //2倍 
struct edge
{
    int x, y, z;
}edges[maxn];
void add_edge(int u, int v)
{
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
    cnt++;
    return;
}               
void pre_process(int cur, int father) //求出所有dp[i][j]，表示i往上走2的j次方步到达的祖先 
{
    vis[cur] = true;
    d[cur] = d[father] + 1; //深度 
    dp[cur][0] = father; //DP的边界条件 
    for(int i = 1; (1 << i) <= d[cur]; i++)
        dp[cur][i] = dp[dp[cur][i-1]][i-1]; //cur的第2的i次方级祖先由2的i-1次方级祖先得到 
    for(int i = head[cur]; i != -1; i = e[i].next)
    {
        int v = e[i].to; //nbr[cur][i];
        if(v != father) //往下求孩子结点 
            pre_process(v, cur);
    }
    return ;
}                               

int lca(int a, int b)  //b在下方  
{
    if(d[a] > d[b])
        swap(a, b); //保证a是在b结点上方，即a的深度小于b的深度
    for(int i = 20; i >= 0; i--) //跳的最大距离是log(深度) 
        if(d[a] <= d[b] - (1 << i)) //把a、b调至 同一个深度
            b = dp[b][i];       
    if(a == b)
        return a;                 
    for(int i = 20; i >= 0; i--)
        if(dp[a][i] != dp[b][i]) //一起上移
        {
            a = dp[a][i];
            b = dp[b][i]; 
        }
    return dp[a][0];  //找出最后a的父亲结点 
}

bool cmp(edge a, edge b)
{
    return a.z > b.z;
}

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

void kruskal()
{
    point = n; //点的编号从n继续计数 
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    sort(edges + 1, edges + m + 1, cmp); //将所有的边排序,注意此题从大到小 
    for(int i = 1; i <= m; i++)
    {
        int a = find(edges[i].x); 
        int b = find(edges[i].y); 
        if(a != b) 
        {
            point++;
            val[point] = edges[i].z;
            fa[a] = fa[b] = fa[point] = point;
            add_edge(a, point);
            add_edge(point, a);
            add_edge(b, point);
            add_edge(point, b);
        }
    }
    return ;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> edges[i].x >> edges[i].y >> edges[i].z;
    memset(head, -1, sizeof(head));
    kruskal();
    for(int i = point; i > n; i--)
        if(vis[i] == false)
            pre_process(i, 0);
    int q; 
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        if(find(x) != find(y))
            cout << -1 << endl;
        else
        {
            int tmp = lca(x, y);
            cout << val[tmp] << endl;
        }
    }
    return 0;
}

还有一道极具挑战性的NOI毒瘤题

P4768 [NOI2018] 归程

按照边权的海拔从大到小排序，建Kruskal重构树；
从点1跑dijkstra(1)，得到dis_x;
dfs跑Kruskal重构树得到每个子树内的最小的dis值ans_x;
对于每一次询问起点v，水位线p，寻找深度最小的祖先节点l，使得height_l>p,则ans_l即为答案;
倍增寻找v对应的点l，时间复杂度O(log_N);

#include<bits/stdc++.h>
using namespace std;
const int N = 8e5 + 5;
#define int long long
struct e
{
    int x, y, w, h;
}edge[N]; 
struct node
{
    int x, dis;
    bool operator < (const node &tmp) const
    {
        return dis > tmp.dis;
    }
};
int T, n, m, q, k, s, tot, last, fa[N], tree[N], dp[N][25], dep[N], dis[N], ans[N];
bool vis[N]; 
vector<node> nbr[N];
vector<int> line[N];
void dijkstra(int s)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    node cur = {s, dis[s]};
    priority_queue<node> pq;
    pq.push(cur);
    while(!pq.empty())
    {
        cur = pq.top();
        pq.pop();
        int x = cur.x;
        if(vis[x])
            continue;
        vis[x] = 1;
        for(int i = 0; i < nbr[x].size(); i++)
        {
            int y = nbr[x][i].x;
            int d = nbr[x][i].dis;
            if(dis[y] > dis[x] + d)
            {
                dis[y] = dis[x] + d;
                node nxt = {y, dis[y]};
                pq.push(nxt);
            }
        }
    }
    return ;
}
int find(int x)
{
    if(fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
bool cmp(e a, e b)
{
    return a.h > b.h;
}
void kruskal()
{
    sort(edge + 1, edge + 1 + m, cmp);
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    tot = n;
    for(int i = 1; i <= m; i++)
    {
        int fx = find(edge[i].x);
        int fy = find(edge[i].y);
        if(fx == fy)
            continue;
        tree[++tot] = edge[i].h;
        fa[fx] = fa[fy] = fa[tot] = tot;
        line[tot].push_back(fx); 
        line[tot].push_back(fy); 
    }
    return ;
}
void dfs_dp(int cur)
{
    ans[cur] = dis[cur];
    for(int i = 0; i < line[cur].size(); i++)
    {
        int nxt = line[cur][i];
        dfs_dp(nxt);
        ans[cur] = min(ans[cur], ans[nxt]);
    }
    return ;
}
void pre_lca(int cur, int fath)
{
    dep[cur] = dep[fath] + 1;
    dp[cur][0] = fath;
    for(int i = 1; (1 << i) <= dep[cur]; i++)
        dp[cur][i] = dp[dp[cur][i-1]][i-1];
    for(int i = 0; i < line[cur].size(); i++)
        pre_lca(line[cur][i], cur);
    return ;
} 
int query(int x, int h)
{
    for(int i = 23; i >= 0; i--)
        if(dp[x][i] && tree[dp[x][i]] > h){
            x = dp[x][i];
        }
    return ans[x];
}
void init()
{
    memset(tree, 0xcf, sizeof(tree));
    memset(ans, 0x3f, sizeof(ans));
    memset(dp, 0, sizeof(dp));
    last = 0;
    for(int i = 1; i <= n + m; i++)
        nbr[i].clear(), line[i].clear();
    return ;
}
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> edge[i].x >> edge[i].y >> edge[i].w >> edge[i].h;
        node t1 = {edge[i].y, edge[i].w};
        nbr[edge[i].x].push_back(t1);
        node t2 = {edge[i].x, edge[i].w};
        nbr[edge[i].y].push_back(t2);
    }
    dijkstra(1);
    kruskal();
    dfs_dp(tot);
    pre_lca(tot, 0); 
    cin >> q >> k >> s;
    while(q--)
    {
        int v, p;
        cin >> v >> p;
        v = (v + k * last - 1) % n + 1;
        p = (p + k * last) % (s + 1);
        last = query(v, p); 
        cout<<last<<'\n';
    }
    return ;

}
signed main()
{
    cin >> T;
    while(T--)
    {
        init();
        solve();
    }
    return 0; 
}

然后还有一道更加毒的题：

P4197 Peaks

思路：

将ｍ条边从大到小排序，建Kruskal重构树，
维护重构树的倍增信息dp_ij；
对于每次询问(v,x)倍增找到深度最浅的ｖ的祖先p，使得val_p<=x；
对于pos所在的子树，找到叶子节点中高度第ｋ大的值；
对于kruskal重构树，跑dfs序，维护每个节点的最早和最晚时间戳st_x，ed_x，并统计每个子树中的叶子的数量leaf_x；
主席树query(st_p,ed_p)区间内的第ｋ大，注意建主席树时只把原图的点建上去；

#include<bits/stdc++.h>
using namespace std;
int read(){
    char cc=getchar();int cn=0,flus=1;
    while(cc < '0' || cc > '9'){
        if(cc == '-') flus=-flus;
        cc=getchar();
    }
    while(cc >= '0' && cc <= '9')
        cn=cn * 10+cc - '0',cc=getchar();
    return cn * flus;
}
const int N=2e5+5;
const int M=5e5+5;
const int inf=999999999;
struct E{
    int to,next;
}e[N * 2];
struct Node{
    int x,y,z;
}q[M],hh[N];
struct Tree{
    int l,r,val;
}Tree[N * 27];
int h[N],head[N],fa[N],val[N],fath[N][24],L[N],R[N],b[N];
int n,m,Q,cnt,tot,pop,rot[N],ctt;
bool cmp(Node x,Node y){
    return x.z < y.z;
}
void add(int x,int y){
    e[++cnt]=(E){y,head[x]};head[x]=cnt;
}
int find(int x){
    if(fa[x] == x)
        return x;
    return fa[x]=find(fa[x]);
}
void Kruskal()
{
    sort(q+1,q+m+1,cmp);
    for(int i=1;i <= n;i++)
        fa[i]=i;
    tot=n;
    for(int i=1;i <= m;i++)
    {
        int fx=find(q[i].x),fy= find(q[i].y);
        if(fx==fy)
            continue;
        val[++tot]=q[i].z,fa[tot]=fa[fx]=fa[fy]=tot;
        add(tot,fx),add(tot,fy);
    }
}
void dfs(int x,int fa)
{
    fath[x][0]=fa;
    for(int i=1;i <= 19;i ++)  
        fath[x][i]=fath[fath[x][i - 1]][i - 1];
    L[x]=pop;
    if(head[x] == 0){
        b[++pop]=x;
        R[x]=pop;
        return ;
    }
    for(int i=head[x];i;i=e[i].next)
        dfs(e[i].to,x);
    R[x]=pop;
}
void build(int &root,int ll,int rr)
{
    root=++ctt;
    if(ll == rr)  return ;
    int mid=(ll+rr) >> 1;
    build(Tree[root].l,ll,mid);
    build(Tree[root].r,mid+1,rr);
}
void update(int &root,int node,int ll,int rr,int k)
{
    root=++ctt;Tree[root]=Tree[node];
    if(ll == rr) { 
        Tree[root].val++;
        return ;
    }
    int mid=(ll+rr) >> 1;
    if(mid >= k)
        update(Tree[root].l,Tree[node].l,ll,mid,k);
    else
        update(Tree[root].r,Tree[node].r,mid+1,rr,k);
    Tree[root].val=Tree[Tree[root].l].val+Tree[Tree[root].r].val;
}
int find_tr(int x,int k)
{
    int now=x;
    for(int i=19;i >= 0;i--)
        if(val[fath[now][i]] <= k) now=fath[now][i];
    return now;
}
int query(int root1,int root2,int k,int l,int r)
{
    int rs=Tree[Tree[root1].r].val - Tree[Tree[root2].r].val,mid=(l+r) >> 1;
    if(l == r){
        if(k - (Tree[root1].val - Tree[root2].val) == 0) 
            return l;
        return 0;
    }
    if(rs >= k)
        return query(Tree[root1].r,Tree[root2].r,k,mid+1,r);
    else
        return query(Tree[root1].l,Tree[root2].l,k - rs,l,mid);
}
signed main()
{
    n=read(),m=read(),Q=read();
    val[0]=inf;
    for(int i=1;i <= n;i++) h[i]=read(),hh[i].x=i,hh[i].z=h[i];
    sort(hh+1,hh+n+1,cmp);
    for(int i=1;i <= n;i++)
        h[hh[i].x]=i;
    for(int i=1;i <= m;i++)
        q[i].x=read(),q[i].y=read(),q[i].z=read();
    Kruskal();
    dfs(tot,tot);
    build(rot[0],1,n);
    for(int i=1;i <= pop;i++)
        update(rot[i],rot[i - 1],1,n,h[b[i]]);
    int v,x,k;
    hh[0].z=-1;
    for(int i=1;i<=Q;i++)
    {
        v=read(),x=read(),k=read();
        int vip=find_tr(v,x);
        int ans=query(rot[R[vip]],rot[L[vip]],k,1,n);
        cout<<hh[ans].z<<'\n';
    }
    return 0;
}

然后就是阴间题目黑暗爆炸-4242 水壶

什么叫做阴间捏，就是老子写kruskal重构树之前他妈要优化建边，这傻逼题目内存开不下，直接建边是N^2的空间复杂度，本来还想要在建筑物之间建边的，结果一看建筑物数p<=2e5,p^2的空间肯定是寄的，所以我们需要建边优化，同机房的dalao说用线段树建边优化，可是萌新不会，于是偷懒的萌新想出来一个也不是很阳光的解法：bfs建边优化，对于从x到y，查找离y最近的建筑物pos_y，然后将pos_x和pos_y建边，是不是非常的简单便捷，正确性的话，或许有人会担心如果y有多个最近的点怎么办，其实并不影响其正确性，因为按照这种方法能够保证pos_y和那个最近的点是间接联通的，明显就不会影响了吧，因为在kruskal中是要对边排序的，所以正确性这点不用担心。

然后我们上代码：

#include<bits/stdc++.h>
using namespace std;
queue<int> q1;
queue<int> q2;
const int N=2e5+5;
int read()
{
    char ch=getchar();int f=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();}
    return f;
}
int fa[N],head[N],dep[N],anc[N][19],tot,cnt,root,ans[N][19];
struct node
{
    int from;
    int to;
    int next;
    int w;
}edge[400005],e[4000005];
int a[2005][2005],dis[2005][2005],n,m,p,q,num,now_color;char s[2005];
int color[N];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void ins(int u,int v,int w)
{
    e[++tot].from=u;
    e[tot].to=v;
    e[tot].w=w;
    e[tot].w=w;
}
void add(int u,int v,int w)
{
    edge[cnt].from=u;
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int cmp(node x,node y)
{
    return x.w<y.w;
}
void bfs()
{
    while(!q1.empty())
    {
        int x=q1.front(),y=q2.front();
        q1.pop();q2.pop();
        if(a[x+1][y]!=-1)
        {
            if(a[x+1][y]==0)
            {
                dis[x+1][y]=dis[x][y]+1;
                a[x+1][y]=a[x][y];
                q1.push(x+1);
                q2.push(y);
            }
            else if(a[x][y]!=a[x+1][y])
            {
                ins(a[x][y],a[x+1][y],dis[x][y]+dis[x+1][y]+1);
            }
        }
        if(a[x][y+1]!=-1)
        {
            if(a[x][y+1]==0)
            {
                dis[x][y+1]=dis[x][y]+1;
                a[x][y+1]=a[x][y];
                q1.push(x);
                q2.push(y+1);
            }
            else if(a[x][y]!=a[x][y+1])
            {
                ins(a[x][y],a[x][y+1],dis[x][y]+dis[x][y+1]+1);
            }
        }
        if(a[x-1][y]!=-1)
        {
            if(a[x-1][y]==0)
            {
                dis[x-1][y]=dis[x][y]+1;
                a[x-1][y]=a[x][y];
                q1.push(x-1);
                q2.push(y);
            }
            else if(a[x][y]!=a[x-1][y])
            {
                ins(a[x][y],a[x-1][y],dis[x][y]+dis[x-1][y]+1);
            }
        }
        if(a[x][y-1]!=-1)
        {
            if(a[x][y-1]==0)
            {
                dis[x][y-1]=dis[x][y]+1;
                a[x][y-1]=a[x][y];
                q1.push(x);
                q2.push(y-1);
            }
            else if(a[x][y]!=a[x][y-1])
            {
                ins(a[x][y],a[x][y-1],dis[x][y]+dis[x][y-1]+1);
            }
        }
    }
}
void dfs(int x)
{
    color[x]=now_color;
    for(int i=1;i<=18;i++)
    {
        if(dep[x]>(1<<i))
        {
            anc[x][i]=anc[anc[x][i-1]][i-1];
            ans[x][i]=max(ans[x][i-1],ans[anc[x][i-1]][i-1]);
        }
        else
        break;
    }
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        if(anc[x][0]!=edge[i].to)
        {
            anc[edge[i].to][0]=x;
            ans[edge[i].to][0]=edge[i].w;
            dep[edge[i].to]=dep[x]+1;
            dfs(edge[i].to);
        }
    }
}
int lca(int x,int y)
{
    int ss=0;
    if(dep[x]<dep[y])
    swap(x,y);
    int d=dep[x]-dep[y];
    for(int i=18;i>=0;i--)
    {
        if(d&(1<<i))
        {
            ss=max(ss,ans[x][i]);
            x=anc[x][i];
        }
    }
    if(x==y)
    return ss;
    for(int i=18;i>=0;i--)
    {
        if(anc[x][i]!=anc[y][i])
        {
            ss=max(ss,ans[x][i]);
            ss=max(ss,ans[y][i]);
            x=anc[x][i];
            y=anc[y][i];
        }
    }
    if(anc[x][0])
    {
        ss=max(ss,ans[x][0]);
        ss=max(ss,ans[y][0]);
    }
    return ss;
}
int main()
{
    memset(a,-1,sizeof(a));
    memset(head,-1,sizeof(head));
    n=read(),m=read(),p=read(),q=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
        {
            if(s[j]=='#')
            a[i][j]=-1;
            else a[i][j]=0;
        }
    }
    for(int i=1;i<=p;i++)
    {
        int x=read(),y=read();
        a[x][y]=i;
        q1.push(x);
        q2.push(y);
    }
    bfs();
    sort(e+1,e+tot+1,cmp);;
    for(int i=1;i<=p;i++)
    fa[i]=i;
    for(int i=1;i<=tot;i++)
    {
        int x=find(e[i].from),y=find(e[i].to);
        if(x!=y)
        {
            add(e[i].from,e[i].to,e[i].w);
            add(e[i].to,e[i].from,e[i].w);
            fa[x]=y;
            num++;
            if(num==p-1)
            break;
        }
    }
    for(int i=1;i<=p;i++)
    {
        if(!color[i])
        {
            now_color++;
            dep[i]=1;
            dfs(i);
        }
    }
    for(int i=1;i<=q;i++)
    {
        int x=read(),y=read();
        if(color[x]!=color[y])
        puts("-1");
        else
        printf("%d\n",lca(x,y)-1);
    }
    return 0;
}