P4180 严格次小生成树[BJWC2010]

àì夳堔傛蜴生んèń 2023-06-04 07:58 148阅读 0赞

**[题目链接][Link 1]**

**当时在暑假早就讲了这道题了，只不过我现在才做了这道题。**

**题解：**

**我们要求次小生成树的话，考虑先把最小生成树求出来，因为如果我们用求最小生成树的话，边早已经从大到小排序好了，所以次小生成树的就是替换最小生成树上的一条边所得。**

**那么考虑如何来替换那一条边，要保证严格次小，那么我们需要替换掉最小生成树上两点间最大的边权，这样暴力枚举删边肯定是不行的，所以我们需要维护在最小生成树上的边。考虑用树链剖分来维护（其实就是打不来倍增）**

**然而维护的时候我们不仅要维护边权的最大值，还不能忘了再维护一个边权的次大值，因为最大值的边权有可能与我们枚举的非树边相等，不满足严格次小，所以还要维护次大值。**

**那么这道题的解法就很容易了，枚举非树边，然后用非树边替换求出次小生成树即可。时间复杂度nlogn+kruskal复杂度。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    const long long inf=1e15;
    struct node{
        int x,y,val,flag;
    }tree[maxn*4];
    bool cmp(node a,node b){
        return a.val<b.val;
    }
    struct dd{
        int nxt,to,val;
    }edge[maxn*3];
    struct sb{
        int l,r;
        long long mx1,mx2;//维护最大值与次大值 
    }seg[maxn*4];
    int n,m,x,y,v;
    int fa[maxn]; 
    int get(int x){
        if(x==fa[x]) return x;
        else return fa[x]=get(fa[x]);
    }
    int head[maxn],cnt;
    void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    long long ans;
    void kruskal(){
        ans=0;
        int tot=0;
        sort(tree+1,tree+1+m,cmp);
        for(int i=1;i<=m;i++){
            int f1=get(tree[i].x);
            int f2=get(tree[i].y);
            if(f1!=f2){
                fa[f1]=f2;
                ans+=tree[i].val;
                tree[i].flag=1;
                tot++;
                if(tot==n-1) break;
            }
        }
        for(int i=1;i<=m;i++){
            if(tree[i].flag){
                add(tree[i].x,tree[i].y,tree[i].val);
                add(tree[i].y,tree[i].x,tree[i].val);
            }
        }
    }
    int w[maxn],dep[maxn],siz[maxn],faa[maxn],son[maxn];
    void dfs1(int x,int f){
        dep[x]=dep[f]+1;
        faa[x]=f;
        siz[x]=1;
        int maxson=-1;
        for(int i=head[x];i;i=edge[i].nxt){
            int go=edge[i].to;
            if(go==faa[x]) continue;
            w[go]=edge[i].val;
            dfs1(go,x);
            siz[x]+=siz[go];
            if(siz[go]>maxson){
                maxson=siz[go];
                son[x]=go;
            }
        }
    }
    int top[maxn],id[maxn],va[maxn],in;
    void dfs2(int x,int topf){
        top[x]=topf;
        id[x]=++in;
        va[id[x]]=w[x];
        if(!son[x]) return;
        dfs2(son[x],topf);
        for(int i=head[x];i;i=edge[i].nxt){
            int go=edge[i].to;
            if(go==faa[x]||go==son[x]) continue;
            dfs2(go,go);
        }
    }
    void pushup(int now){
        if(seg[now<<1].mx1>seg[now<<1|1].mx1){
            seg[now].mx1=seg[now<<1].mx1;
            seg[now].mx2=max(seg[now<<1].mx2,seg[now<<1|1].mx1);
        }
        if(seg[now<<1].mx1<seg[now<<1|1].mx1){
            seg[now].mx1=seg[now<<1|1].mx1;
            seg[now].mx2=max(seg[now<<1].mx1,seg[now<<1|1].mx2);
        }
        if(seg[now<<1].mx1==seg[now<<1|1].mx1){
            seg[now].mx1=seg[now<<1].mx1;
            seg[now].mx2=max(seg[now<<1].mx2,seg[now<<1|1].mx2);
        }
    }
    void build(int now,int l,int r){
        seg[now].l=l,seg[now].r=r;
        if(l==r){
            seg[now].mx1=va[l];
            return;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        pushup(now);
    }
    pair<int,int> getmax(pair<int,int> x,pair<int,int> y){
        int ans1,ans2;
        if(x.first>y.first){
            ans1=x.first;
            ans2=max(x.second,y.first);
        }
        if(x.first<y.first){
            ans1=y.first;
            ans2=max(x.first,y.second);
        }
        if(x.first==y.first){
            ans1=x.first;
            ans2=max(x.second,y.second);
        }
        return make_pair(ans1,ans2);
    }
    pair<int,int> query(int now,int l,int r){
        if(seg[now].l>=l&&seg[now].r<=r) return make_pair(seg[now].mx1,seg[now].mx2);
        int mid=(seg[now].l+seg[now].r)>>1;
        pair<int,int> ans;
        if(l<=mid) ans=getmax(ans,query(now<<1,l,r));
        if(r>mid) ans=getmax(ans,query(now<<1|1,l,r));
        return ans;
    }
    pair<int,int> link(int x,int y){
        pair<int,int> res;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            res=getmax(res,query(1,id[top[x]],id[x]));
            x=faa[top[x]];
        }
        if(dep[x]<dep[y]) swap(x,y);
        res=getmax(res,query(1,id[y]+1,id[x]));
        return res;
    }
    void solve(){
        pair<int,int> ass;
        long long save;
        long long final=inf;
        for(int i=1;i<=m;i++){
            if(!tree[i].flag){
                ass=link(tree[i].x,tree[i].y);
                if(tree[i].val>ass.first){ 
                    save=ans;
                    final=min(final,save-ass.first+tree[i].val);
                }
                else if(tree[i].val>ass.second){
                    save=ans;
                    final=min(final,save-ass.second+tree[i].val);
                }
            }
        }
        printf("%lld\n",final);
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++) scanf("%d%d%d",&tree[i].x,&tree[i].y,&tree[i].val);
        kruskal();
        dfs1(1,0);dfs2(1,1);build(1,1,n);
        solve();
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11628054.html

[Link 1]: https://www.luogu.org/problem/P4180
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/5bb0a0ecb01e4d158afb31d7af62c113.png