【算法】严格次小生成树 [BJWC2010] —B_Z_B_Y

于由B_Z_B_Y发布

HAPPY Studying OvO

题意：设最小生成树的边权之和为 $ sum$，严格次小生成树就是指边权之和大于 $sum$ 的生成树中最小的一个。

思路 ： Kruskal + LCA

步骤：

1. 首先你得会 Kruskal 和 LCA （不会的话请先去学习一下 QwQ）
2.Kruskal 求出最小生成树
3.LCA 初始化边权，存最大值和次大值
4. 求次小生成树， 至于严不严格 就是边权之和是大于 $sum$，还是边权之和大于等于 $sum$ 而已

First. Kruskal

将边 按照边权从小到大排序 , 扫描时 并查集判断，如果不在联通块内就连边

void Kruskal(){
    sort(a+1,a+1+m);//a 存的是初始化的边集

    fors(i,1,n) f[i]=i;//并查集

    fors(i,1,m){
        int as=find(a[i].u),bs=find(a[i].v);
        if(as != bs){
            cnt+=a[i].val;//最小生成树边权和
            f[bs]=as;
            add(a[i].u,a[i].v,a[i].val);
            add(a[i].v,a[i].u,a[i].val);//把最小生成树的边以邻接表存起来
            vis[i]=1;//存点
        }
    }
}

—

Second. LCA

树上倍增： 用 $bz[~]$存一下，$bz[i]~[j]$表示 $i$点上面的第 $2^j$个祖先

$minai[~]$存次大边权，$maxai[~]$存最大边权

void dfs(int u,int fa){
    bz[u][0]=fa;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v == fa) continue;
        depth[v]=depth[u]+1ll;
        maxai[v][0]=edge[i].val;
        minai[v][0]=-inf;//先极小值
        dfs(v,u);//u 是目标节点，v 是起始节点
    }
}//dfs 建树
//minai 存次大边权，maxai 存最大边权
void cal(){
    fors(j,1,18)
        fors(i,1,n){
            bz[i][j]=bz[bz[i][j-1]][j-1];
            maxai[i][j]=max(maxai[i][j-1],maxai[bz[i][j-1]][j-1]);
            minai[i][j]=min(minai[i][j-1],minai[bz[i][j-1]][j-1]);//预处理

            if(maxai[i][j-1] > maxai[bz[i][j-1]][j-1]) 
                minai[i][j]=max(minai[i][j],maxai[bz[i][j-1]][j-1]);
            else if(maxai[i][j-1] < maxai[bz[i][j-1]][j-1]) 
                     minai[i][j]=max(minai[i][j],maxai[i][j-1]);//minai 存次大边权
        }
}

int lca(int x,int y){
    if(depth[x] < depth[y]) swap(x,y);

    for(int i=18;i>=0;--i)
        if(depth[bz[x][i]] >= depth[y])
            x=bz[x][i];
    if(x==y) return x;

    for(int i=18;i >= 0 ;--i)
        if(bz[x][i] != bz[y][i])
            x=bz[x][i],y=bz[y][i];
    return bz[x][0];
}

—

Third. 求严格次小生成树

遍历每条未选的边 $(u,v,val)$，对于这条路径，我们断掉最大边（肯定 $val$不超过最大边）。这就找到了次大生成树，但是不一定是严格的。所以我们计算这条链上边权的严格次大值，然后如果最大值和这条边权相等就断严格次大边。然后一直 $min$边权就 OK 了 OvO


int querymax(int u,int v,int maxs){
    int ans=-inf;
    ford(int i=18;i>=0;--i)
        if(depth[bz[u][i]] >= depth[v]){
            if(maxs != maxai[u][i]) ans=max(ans,maxai[u][i]);
            else ans=max(ans,minai[u][i]);//上述操作
            u=bz[u][i];
        }
    return ans;
}//求最大的 u 或 v

signed main()
{
    n=read(),m=read();
    fors(i,1,m)
        a[i].u=read(),a[i].v=read(),a[i].val=read();

    Kruskal();
    minai[1][0]=-inf;
    depth[1]=1;
    dfs(1,-1);
    cal();

    int ans=inf;
    fors(i,1,m){
        if(!vis[i]){//遍历未加入最小生成树的点

            int u=a[i].u,v=a[i].v,val=a[i].val;
            int lcas=lca(u,v),maxsu=querymax(u,lcas,val),maxsv=querymax(v,lcas,val);
            ans=min(ans,cnt-max(maxsu,maxsv)+val);//cnt 是最小生成树边权和

        }
    }
    printf("%lld\n",ans);
    return 0;
}

—

Finally . 整合起来就完成了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define int long long//由于精度要求 int-ll
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y))
const int maxn=1e6+7;
const int inf=1ll<<60;
const int Size=1<<25;
inline char getch(){
    static char buf[Size],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2) ? EOF : *p1++;
}
int read(){
    int f=1,s=0;
    char c=getch();
    while(c<'0' || c>'9'){if(c=='-') f=-1; c=getch();}
    while(c<='9' && c>='0') {s=s*10+c-48;c=getch();}
    return s*f;
}
//卡常使我快乐 *v*
struct node
{
    int u,v,val,next;
    bool operator < (const node &ano) const {
        return val < ano.val;
    }
}edge[maxn<<1];

int m,n,tot,head[maxn],bz[maxn][19],maxai[maxn][19],minai[maxn][19],depth[maxn];

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

void dfs(int u,int fa){
    bz[u][0]=fa;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v == fa) continue;
        depth[v]=depth[u]+1ll;
        maxai[v][0]=edge[i].val;
        minai[v][0]=-inf;
        dfs(v,u);
    }
}

void cal(){
    fors(j,1,18)
        fors(i,1,n){
            bz[i][j]=bz[bz[i][j-1]][j-1];
            maxai[i][j]=max(maxai[i][j-1],maxai[bz[i][j-1]][j-1]);
            minai[i][j]=min(minai[i][j-1],minai[bz[i][j-1]][j-1]);

            if(maxai[i][j-1] > maxai[bz[i][j-1]][j-1]) 
                minai[i][j]=max(minai[i][j],maxai[bz[i][j-1]][j-1]);
            else if(maxai[i][j-1] < maxai[bz[i][j-1]][j-1]) 
                     minai[i][j]=max(minai[i][j],maxai[i][j-1]);
        }
}

int lca(int x,int y){
    if(depth[x] < depth[y]) swap(x,y);

    for(int i=18;i>=0;--i)
        if(depth[bz[x][i]] >= depth[y])
            x=bz[x][i];
    if(x==y) return x;

    for(int i=18;i >= 0 ;--i)
        if(bz[x][i] != bz[y][i])
            x=bz[x][i],y=bz[y][i];
    return bz[x][0];
}


int querymax(int u,int v,int maxs){
    int ans=-inf;
    for(int i=18;i>=0;--i)
        if(depth[bz[u][i]] >= depth[v]){
            if(maxs != maxai[u][i]) ans=max(ans,maxai[u][i]);
            else ans=max(ans,minai[u][i]);
            u=bz[u][i];
        }
    return ans;
}


node a[maxn<<1];

int f[maxn];

int find(int x){
    return x==f[x] ? x : f[x]=find(f[x]);
}

bool vis[maxn<<1];

int cnt;

void Kruskal(){
    sort(a+1,a+1+m);

    fors(i,1,n) f[i]=i;

    fors(i,1,m){
        int as=find(a[i].u),bs=find(a[i].v);
        if(as != bs){
            cnt+=a[i].val;
            f[bs]=as;
            add(a[i].u,a[i].v,a[i].val);
            add(a[i].v,a[i].u,a[i].val);
            vis[i]=1;
        }
    }
}

signed main()
{
    n=read(),m=read();
    fors(i,1,m)
        a[i].u=read(),a[i].v=read(),a[i].val=read();

    Kruskal();
    minai[1][0]=-inf;
    depth[1]=1;
    dfs(1,-1);
    cal();

    int ans=inf;
    fors(i,1,m){
        if(!vis[i]){

            int u=a[i].u,v=a[i].v,val=a[i].val;
            int lcas=lca(u,v),maxsu=querymax(u,lcas,val),maxsv=querymax(v,lcas,val);
            ans=min(ans,cnt-max(maxsu,maxsv)+val);

        }
    }
    printf("%lld\n",ans);
    return 0;
}
分类： 文章

B_Z_B_Y

Let us go go go！！！！！！ 　☆ *　. 　☆ 　　. ∧＿∧　∩　* ☆ * ☆ ( ・∀・)/ . 　. ⊂　　 ノ* ☆ ☆ * (つ ノ .☆ 　　 (ノ

7 条评论

SEP · 2018年10月12日 5:54 下午

QAQ 居然回复我了。。。

回复

SEP · 2018年10月10日 7:17 下午

黑书上有更方便的算法，可以参考 O(∩_∩)O

回复

    B_Z_B_Y · 2018年10月11日 8:34 下午

    真的吗？ 可以发给我看看吗？ OvO 不过说起来黑书是啥？

    回复

      XZYQvQ · 2018年10月11日 9:07 下午

      黑书->算法艺术与信息学竞赛

      回复

        B_Z_B_Y · 2018年10月12日 9:23 上午

        Thank you ！， 我竟然只找到了 pdf 版的 2333

        回复

          SEP · 2018年10月12日 5:53 下午

          算法导论（当时还是后面的思考题，官网有解答）

          回复

            XZYQvQ · 2018年10月12日 6:33 下午

            QvQ 我被我儿子坑了，我一开始一位是算导然而我 Naive 了 QwQ
            （光速逃

            回复

回复 SEP 取消回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注