树论入门(二)

树论入门(二)

0 说明

前备知识可看图论入门(一)

以下的算法复杂度分析中,n为图中点的数量,m为图中边的数量

1 最小生成树

1.1 生成树与最小生成树

在图论中,无向图的生成树是具有无向图的全部顶点,但边数最少(可以知道最少边数为n-1)的连通子图

最小生成树,全称最小权重生成树,是一副联通加权无向图中一棵权值最小的生成树。下图演示的就是从一棵最小生成树

求最小生成树采用贪心策略,有两种算法,分别是Prim,Kruskal。

1.2 Prim

Prim算法,于1930年由捷克数学家沃伊捷赫·亚尔尼克发现。Prim算法主要有以下操作:

  • 首先将点分为两部分,已选择的部分的和未选择的部分,初始所有点都在未选择的部分
  • 先随机选取一个点作为初始点,每一步从连接未选择部分的点的边中,选取一条权值最小的,将对应边加入最小生成树,将对应点加入已选择的部分

大致上来说,Prim算法与Dijkstra算法很像。Prim算法的实现方式有三种,这里只讲基本枚举和二叉堆优化。

  • 基本枚举

这种方法就是把所有点都跑一遍。一共要跑n次,一次要从n个结点中找到最小的结点,所以这种方法的时间复杂度为$O(n^2)$。请看代码。

  • 例1.2.1
struct Edge
{
    int v;
    int w;
    int next;
}edge[1000005];

int head[200005];
int cnt;
bool vis[200005];
unsigned F[200005];

void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
	    int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    
    memset(F,0xFF,sizeof(F));

    int x=1;
    F[x]=0;
    int ans=0;
    int pick=0;

    while(!vis[x]&&++pick<n)
    {
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            if(!vis[edge[i].v]&&F[edge[i].v]>edge[i].w)
                F[edge[i].v]=edge[i].w;
        }

        int minn=INT_MAX;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&minn>F[i])    //取新的最小值
            {
                minn=F[i];
                x=i;
            }
        }
        ans+=minn;
    }

    cout<<ans<<'\n';
    return 0;
}
  • 二叉堆优化

所谓二叉堆优化可以理解为就是用优先队列(类似二叉堆)来优化每次选取最小的F[]的过程,所以这种方法的时间复杂度为$O((m+n)logm)$,请看代码。

  • 例1.2.2
struct Edge
{
    int v;
    int w;
    int next;
}edge[1000005];

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
int head[200005];
int cnt;
bool vis[200005];
unsigned F[200005];

void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    
    memset(F,0xFF,sizeof(F));

    F[1]=0;
    q.push(make_pair(0,1));
    int ans=0;
    
    while(!q.empty())
    {
        pair<int,int> temp=q.top();
        int x=temp.second;
        q.pop();
        if (vis[x]) continue;
        ans+=temp.first;
        vis[x]=1;
        
        for(int i=head[x];i;i=edge[i].next)
        {
            if(!vis[edge[i].v]&&F[edge[i].v]>edge[i].w)
            {
                F[edge[i].v]=edge[i].w;
                q.push(make_pair(F[edge[i].v],edge[i].v));
            }
        }
    }

    cout<<ans<<'\n';
    return 0;
}

1.4 Kruskal算法

Kruskal算法,由Joseph Kruskal在1956年发表。Kruskal使用并查集维护树的连通性,它的具体操作是:

  • 首先将所有的边按从小到大顺序排序(一般使用快排),并认为每一个点都是孤立的
  • 按从小到大的顺序枚举每一条边。
  • 如果这条边连接着两个点不在一个连通块,那么就把这条边加入最小生成树,将两个连通块合并。如果这条边连接的两个点在一个连通块,就跳过。直到选取了n-1条边为止。

操作的演示图如上。接下来请看代码。

  • 例1.4.1
struct node
{
    int u,v,w;
}edge[1000005];

int fa[200005];
int connected[200005];
int ans;

int check_anc(int x)    //寻找祖先
{
    if (fa[x]) return fa[x]=check_anc(fa[x]);
    return x;
}
void union_anc(int x,int y)    //合并和计算最大联通数
{
    x=check_anc(x); y=check_anc(y);
    if (x!=y)
    {
	fa[x]=y;
	connected[y]+=connected[x];
        if (connected[y]>ans)
            ans=connected[y];
    }
}
bool is_same_anc(int x,int y)    //是否有相同祖先
{
    if (check_anc(x)==check_anc(y)) return 1;
    else return 0;
}

bool cmp(node x,node y)
{
    return x.w<y.w;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;

    for (int i=1;i<=n;i++)
        connected[i]=1;
    
    for (int i=0;i<m;i++)
        cin>>edge[i].u>>edge[i].v>>edge[i].w;

    sort(edge,edge+m,cmp);

    int sum=0;
    for (int i=0;i<m;i++)
    {
        if (is_same_anc(edge[i].u,edge[i].v)) continue;
        else 
            {union_anc(edge[i].u,edge[i].v); sum+=edge[i].w;}
        if (ans==n) {cout<<sum<<'\n'; return 0;}
    }

    cout<<"Not connected\n";
}

Kruskal算法的平均时间复杂度为$O(mlogn)$。

2 树DP基础

2.1 树的重心

对于树上的每一个结点,计算其所有子树中最大的子树结点数,这个值最小的点就是这棵树的重心。树的重心有许多的性质:

  • 以树的重心为根时,所有子树的大小都不超过整棵树大小的一半。
  • 树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么到它们的距离和一样。
  • 把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两棵树的重心的路径上。
  • 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。

2.2 树上DP

树的重心可以用树上DP(dfs)求。对于每个结点求出最多结点的子树是多少然后再比较就好了。

具体操作是:

  1. 把结点1看作根结点,进行dfs遍历
  2. 计算完每个结点求出最多结点的子树的结点数后与该结点父结点子树的结点数比较,取大的值,如果它比之前求得的值要大,就更新重心结点编号为该结点
  3. 注意:自己的父结点也是自己的一颗子树,所以在取最优时也要与父结点进行比较

转换为DP的形态是这样的:

  • 状态:创建一个变量g,存储重心编号
  • 转移方程:从该结点最大子树结点数与该结点父亲结点子树的结点数中取大的值,如果该大的值大于原先求得的大的值,更新g
  • 初始条件:所有的叶结点的最大子树结点数为0

接下来请看代码。

  • 例2.2.1
struct Edge
{
    int v;
    int w;
    int next;
}edge[1000005];

int head[200005];
int cnt;
int n,m;
int size[200005];
int sub_cnt[200005];
int g;    //存储重心编号

void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void getcenter_g(int x,int fa)
{
    size[x]=1;      //总结点数-该结点父亲结点子树的结点数
    sub_cnt[x]=0;    //该结点除父亲结点子树以外最大子树结点数
    for (int i=head[x];i;i=edge[i].next) 
    {
        int y=edge[i].v;
        if (y!=fa) 
        {
            getcenter_g(y,x);
            size[x]+=size[y];
            sub_cnt[x]=max(sub_cnt[x], size[y]);
        }
    }
    sub_cnt[x]=max(sub_cnt[x],n-size[x]);
    if (g==0||sub_cnt[x]<sub_cnt[g]) g=x;
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }

    getcenter_g(1,0);

    for (int i=1;i<=n;i++)    //可能会有两个重心,再遍历一遍
        if (g!=i&&sub_cnt[g]==sub_cnt[i])
            cout<<i<<' ';
    cout<<g<<'\n';
    return 0;
}

感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。