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
            (光速逃

发表回复

Avatar placeholder

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