欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

严格次小生成树

程序员文章站 2022-06-22 10:17:02
题目描述 小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的。 这下小 C 蒙了,他找到了你,希望你帮他解决这个问题。 输入格式 第一行包含两个整数 ......

题目描述

小c最近学了很多最小生成树的算法,prim算法、kurskal算法、消圈算法等等。正当小c洋洋得意之时,小p又来泼小c冷水了。小p说,让小c求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的。

这下小 c 蒙了,他找到了你,希望你帮他解决这个问题。

输入格式

第一行包含两个整数n 和m,表示无向图的点数与边数。 接下来 m行,每行 3个数x y z 表示,点 x 和点y之间有一条边,边的权值为z。

输出格式

包含一行,仅一个数,表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

洛谷p4180

分析:看到这个题的第一眼想到的是枚举,把所有生成树枚举一遍求最小的,但是显然不行,因为数据有些大了。

想一下最小生成树的算法?kurskal是通过每一次加最小边来实现最小树,所以我们考虑一下边。

对于一棵最小生成树而言,删去树上一边,再加上一条边维护树,就有可能构成次小生成树,为保证它是严格的,所以还要再判断这条边与删去的边是否相等。

现在我们考虑删边,如何保证删去边再加上边仍然是树呢?显然先加边,然后看这条边与其他边构成的环中,最大的那条边是多少,为什么要用最大边呢,因为要求的是次小生成树,在一个点附近,加完边后剩下的边一定大于等于加上的边,不然根据kurskal不会把这条边加上,但这条边还有可能和加的边相等,所以在记录最大边的同时还要记录次大边。

删边和加边的问题解决了,接下来就是记录了,关于记录,使用lca是我没有想到的。

为什么要用lca呢?加边后构成的环,不考虑加的这条边的话,可以分成两部分,一是从边的from到lca,二是从边的to到lca,所以在跑倍增lca的同时(顺便)维护一下最大值和次大值。

最后就是计算了,计算的时候也是同上分两部分,记得判断最大值是不是和边权一样,如果是的话要用次大值。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int n=1e5+10;
//前向星存边
struct edge{
    int to,from,next,val;
    bool isin;
    edge(){isin=val=next=0;}
    bool operator < (const edge &a)const {
        return val<a.val;
    }
}e[n<<1],e[n*3];
int len,head[n];
void ins(int a,int b,int c){
    e[++len].to=b;e[len].val=c;
    e[len].next=head[a];head[a]=len;
}
//并查集+kurskal
int f[n],m,n;
int find(int x){
    return f[x]==x?x:(f[x]=find(f[x]));
}
int ans=0x3f3f3f3f;long long tot=0;
void krs(){
    int cnt=1;
    sort(e+1,e+m+1);
    for(int i=1;cnt<n;i++){
        int v=e[i].to,u=e[i].from;
        if(find(v)!=find(u)){
            cnt++;
            e[i].isin=1;
            tot+=e[i].val;//计算最小生成树
            ins(u,v,e[i].val);
            ins(v,u,e[i].val);
            f[find(v)]=find(u);
        }
    }
}
//倍增lca板子
int dep[n],p[n][20],max[n][20],smax[n][20];
void dfs(int x){
    for(int i=0;p[x][i];i++){
        p[x][i+1]=p[p[x][i]][i];
        max[x][i+1]=max(max[x][i],max[p[x][i]][i]);
        //注意求次大的时候看看两段的最大值是不是相等,如果不判断的话
        //在最大值相等的时候,次大值会被更新为最大值
        if(max[x][i]==max[p[x][i]][i])    
            smax[x][i+1]=max(smax[x][i],smax[p[x][i]][i]);
        else 
            smax[x][i+1]=max(min(max[x][i],max[p[x][i]][i]),
                            max(smax[x][i],smax[p[x][i]][i]));
    }
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v!=p[x][0]){
            dep[v]=dep[x]+1;
            max[v][0]=e[i].val;
            smax[v][0]=-1;
            p[v][0]=x;
            dfs(v);
        }
    }
}
//这段和lca板子一模一样
int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    int d=dep[a]-dep[b];
    for(int i=0;d;i++,d>>=1)
        if(d&1)a=p[a][i];
    if(a==b)return a;
    for(int i=18;i>=0;i--)
        if(p[a][i]!=p[b][i])
            a=p[a][i],b=p[b][i];
    return p[a][0];
}
//计算
void calc(int u,int v,int w){
    int d=dep[u]-dep[v];//深度差,判断路径
    int m1=0,m2=0;
    for(int i=0;d;i++,d>>=1){
        if(d&1){//如果可以往上跳
            m2=max(m2,smax[u][i]);//细节,先求次大值
            if(max[u][i]>m1){//如果更新最大值,那么原来的最大值m1可能为新的次大值
                m2=max(m2,m1);//判断次大值是否更新
                m1=max[u][i];//更新最大值
            }
        }
    }
    if(m1==w)ans=min(ans,w-m2);//如果最大值与边相等,用次大值更新
    else ans=min(ans,w-m1);//否则用最大值
}
int main(){
//    freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);
    krs();
    dfs(1);
    for(int i=1;i<=m;i++){
        if(!e[i].isin){
            int u=e[i].from,v=e[i].to,lca;
            lca=lca(u,v);
            calc(u,lca,e[i].val);
            calc(v,lca,e[i].val);
        }
    }
    printf("%lld\n",tot+ans);
}