正文

Luogu P4180 【模板】严格次小生成树[BJWC2010]

IP云
IP云V管理员/5 阅读
12/01
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

P4180 【模板】严格次小生成树[BJWC2010]

题意

题目描述

小\(C\)最近学了很多最小生成树的算法，\(Prim\)算法、\(Kurskal\)算法、消圈算法等等。正当小\(C\)洋洋得意之时，小\(P\)又来泼小\(C\)冷水了。小\(P\)说，让小\(C\)求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是\(E_M\)，严格次小生成树选择的边集是\(E_S\)，那么需要满足：(\(value(e)\)表示边\(e\)的权值)\(\sum_{e\in E_M}value(e)<\sum_{e\in E_S}value(e)\)

这下小\(C\)蒙了，他找到了你，希望你帮他解决这个问题。

输入输出格式

输入格式：

第一行包含两个整数\(N\)和\(M\)，表示无向图的点数与边数。接下来\(M\)行，每行\(3\)个数\(x\ y\ z\)表示，点\(x\)和点\(y\)之间有一条边，边的权值为\(z\)。

输出格式：

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

输入输出样例

输入样例#1： 

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

输出样例#1： 

11

说明

数据中无向图无自环；

\(50\%\)的数据\(N\leq 2000,M\leq 3000\)；

\(80\%\)的数据\(N≤50 000 M≤100 000\)；

\(100\%\)的数据\(N≤100000,M≤300000\)，边权值非负且不超过\(10^9\)。

思路

先考虑不严格怎么做。先建出最小生成树，然后对每一条不在树上的边进行考虑：加入这条边之后，树上就会多出来一个环，我们把环上最长的一条边删除，就可以得到另一棵生成树。这样产生的生成树里最小的，就是非严格次小生成树了。

得到环上最长的一条边，只需要在原树上求新加边的两顶点之间的\(LCA\)，顺便查询最长边就好了。

之所以不是严格的，是因为加入一条边之后删除的边可能与加入的边的边权相同。这样的话，我们就在预处理倍增记录两点最长边的同时记录两点严格次长边，把它去掉，再加入新边，这样就能求得严格次小生成树了。

AC代码 
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<LL,LL> PLL;

const LL MAXN=1e5+5,MAXM=3e5+5;

LL n,m,ans=LLONG_MAX,sum,dad[MAXN],dep[MAXN];

LL cnt,top[MAXN],to[MAXM<<1],len[MAXM<<1],nex[MAXM<<1];

LL fa[MAXN][20],mx1[MAXN][20],mx2[MAXN][20];

struct Edge

{

    LL u,v,d;

    bool use;

    bool operator < (const Edge &sjf) const {return d<sjf.d;}

}edge[MAXM];

LL read()

{

    LL re=0;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

void add_edge(LL x,LL y,LL z)

{

    to[++cnt]=y,len[cnt]=z,nex[cnt]=top[x],top[x]=cnt;

    to[++cnt]=x,len[cnt]=z,nex[cnt]=top[y],top[y]=cnt;

}

LL fd(LL x)

{

    LL r=x;

    while(r!=dad[r]) r=dad[r];

    LL i=x,j;

    while(i!=r) j=dad[i],dad[i]=r,i=j;

    return r;

}

void Kruskal()

{

    for(LL i=1;i<=n;i++) dad[i]=i;

    for(LL i=0;i<m;i++)

    {

        LL fu=fd(edge[i].u),fv=fd(edge[i].v);

        if(fu!=fv) dad[fu]=fv,edge[i].use=true,sum+=edge[i].d,add_edge(edge[i].u,edge[i].v,edge[i].d);

    }

}

void dfs(LL now)

{

    for(LL i=1;i<=18;i++)

    {

        fa[now][i]=fa[fa[now][i-1]][i-1];

        mx1[now][i]=max(mx1[now][i-1],mx1[fa[now][i-1]][i-1]);

        if(mx1[now][i-1]>mx1[fa[now][i-1]][i-1]) mx2[now][i]=max(mx2[now][i-1],mx1[fa[now][i-1]][i-1]);

        else if(mx1[now][i-1]<mx1[fa[now][i-1]][i-1]) mx2[now][i]=max(mx1[now][i-1],mx2[fa[now][i-1]][i-1]);

        else if(mx1[now][i-1]==mx1[fa[now][i-1]][i-1]) mx2[now][i]=max(mx2[now][i-1],mx2[fa[now][i-1]][i-1]);

    }

    for(LL i=top[now];i;i=nex[i])

    {

        if(to[i]==fa[now][0]) continue;

        fa[to[i]][0]=now,mx1[to[i]][0]=len[i],dep[to[i]]=dep[now]+1;

        dfs(to[i]);

    }

}

PLL LCA(LL x,LL y)

{

    PLL re;re.first=re.second=0;

    if(dep[x]<dep[y]) swap(x,y);

    for(LL i=18;i>=0;i--)

        if(dep[fa[x][i]]>=dep[y])

        {

            if(mx1[x][i]>re.first) re.second=re.first,re.first=mx1[x][i];

            else if(mx1[x][i]>re.second) re.second=mx1[x][i];

            else if(mx2[x][i]>re.second) re.second=mx2[x][i];

            x=fa[x][i];

        }

    if(x==y) return re;

    for(LL i=18;i>=0;i--)

        if(fa[x][i]!=fa[y][i])

        {

            if(mx1[x][i]>re.first) re.second=re.first,re.first=mx1[x][i];

            else if(mx1[x][i]>re.second) re.second=mx1[x][i];

            else if(mx2[x][i]>re.second) re.second=mx2[x][i];

            x=fa[x][i];

            if(mx1[y][i]>re.first) re.second=re.first,re.first=mx1[y][i];

            else if(mx1[y][i]>re.second) re.second=mx1[y][i];

            else if(mx2[y][i]>re.second) re.second=mx2[y][i];

            y=fa[y][i];

        }

    if(mx1[x][0]>re.first) re.second=re.first,re.first=mx1[x][0];

    else if(mx1[x][0]>re.second) re.second=mx1[x][0];

    else if(mx2[x][0]>re.second) re.second=mx2[x][0];

    x=fa[x][0];

    if(mx1[y][0]>re.first) re.second=re.first,re.first=mx1[y][0];

    else if(mx1[y][0]>re.second) re.second=mx1[y][0];

    else if(mx2[y][0]>re.second) re.second=mx2[y][0];

    y=fa[y][0];

    return re;

}

int main()

{

    n=read(),m=read();

    for(LL i=0;i<m;i++) edge[i].u=read(),edge[i].v=read(),edge[i].d=read();

    sort(edge,edge+m);

    Kruskal();

    dep[1]=1;

    dfs(1);

    for(LL i=0;i<m;i++)

    {

        if(edge[i].use) continue;

        PLL hjj=LCA(edge[i].u,edge[i].v);

        if(edge[i].d!=hjj.first) ans=min(ans,sum-hjj.first+edge[i].d);

        else if(hjj.second) ans=min(ans,sum-hjj.second+edge[i].d);

    }

    printf("%lld",ans);

    return 0;

}

相关阅读

目录[+]