洛谷P4180 题解

题目链接

\(Solution:\)

看到标题，想到\(MST\)
我们再考虑次小生成树，在原来的\(MST\)加上一条非树边\((u,v)\)，会跟原本\(MST\)上连接\((u,v)\)的路径形成一个环
这启发我们考虑在环上寻找次小值
我们维护一个\(DP\)数组\(g[i][j][0/1]\)表示\(i\)到\(i\)的\(2^j\)倍祖先路径上的最小，次小值，有状态转移方程：
\(g[i][j][0]=max(g[f[i][j-1]][j-1][0],g[i][j-1][0])\)

\[g[i][j][1]= \begin{cases} max(g[f[i][j-1]][j-1][1],g[i][j-1][1])& \text{g[i][j-1][0]==g[f[i][j-1]][j-1][0]}\max(g[f[i][j-1]][j-1][1],g[i][j-1][0])& \text{g[i][j-1][0]<g[f[i][j-1]][j-1][0]}\max(g[f[i][j-1]][j-1][0],g[i][j-1][1])& \text{g[i][j-1][0]>g[f[i][j-1]][j-1][0]} \end{cases}\]
每次我们枚举一条非树边\((u,v)\)，令\(LCA=lca(u,v)\)，用倍增查询\(u\)到\(LCA\)，\(v\)到\(LCA\)的次小值，即为我们所查询的环上的最小值

\(Code:\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e17;
ll n,m,u,v,w,cnt,head[1000050],f[1000050][30],g[1000050][30][2],dep[1000050],fa[1000050],vis[2000050],ans;
struct edge
{
    ll to,nxt,w;
}e[1000050];
struct Edge
{
    ll u,v,w;
}ed[1000050];
bool operator<(Edge a,Edge b)
{
    return a.w<b.w;
}
inline ll find(ll x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void add(ll u,ll v,ll w)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}
void dfs(ll u,ll fa)
{
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(ll i=head[u];i;i=e[i].nxt)
    {
        ll v=e[i].to;
        if(v==fa) continue;
        f[v][0]=u;
        g[v][0][0]=e[i].w;
        g[v][0][1]=-INF;
        dfs(v,u);
    }
}
ll lca(ll x,ll y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(ll i=20;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(ll i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
ll up(ll u,ll v,ll w)
{
    ll res=-INF;
    for(ll i=20;i>=0;i--)
    {
        if(dep[f[u][i]]>=dep[v])
        {
            if(w==g[u][i][0]) res=max(res,g[u][i][1]);
            else res=max(res,g[u][i][0]);
            u=f[u][i];
        }
    }
    return res;
}
ll work(ll i)
{
    ll u=ed[i].u,v=ed[i].v,rt=lca(u,v);
    ll tmp1=up(u,rt,ed[i].w),tmp2=up(v,rt,ed[i].w);
    return ed[i].w-max(tmp1,tmp2);
}
int main(void)
{
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        ed[i].u=u,ed[i].v=v,ed[i].w=w;
    }
    sort(ed+1,ed+m+1);
    for(ll i=1;i<=n;i++) fa[i]=i;
    ll tmp=0;
    for(ll i=1;i<=m;i++)
    {
        ll a=ed[i].u,b=ed[i].v;
        ll fx=find(a),fy=find(b);
        if(fx==fy) continue;
        fa[fx]=fy;
        vis[i]=1;
        ans+=ed[i].w,tmp++;
        add(a,b,ed[i].w);
        add(b,a,ed[i].w);
        if(tmp==n-1) break;
    }
    dfs(1,0);
    g[1][0][1]=-INF;
    for(ll j=1;j<=20;j++)
    {
        for(ll i=1;i<=n;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j][0]=max(g[f[i][j-1]][j-1][0],g[i][j-1][0]);
            if(g[i][j-1][0]==g[f[i][j-1]][j-1][0]) g[i][j][1]=max(g[f[i][j-1]][j-1][1],g[i][j-1][1]);
            else if(g[i][j-1][0]<g[f[i][j-1]][j-1][0]) g[i][j][1]=max(g[f[i][j-1]][j-1][1],g[i][j-1][0]);
            else g[i][j][1]=max(g[f[i][j-1]][j-1][0],g[i][j-1][1]);
         } 
    }
    ll haha=INF;
    for(ll i=1;i<=m;i++)
    {
        if(!vis[i])
        {
            haha=min(haha,ans+work(i));
        }
    }
    printf("%lld\n",haha);
    return 0;
}

洛谷P4180 题解

原文：https://www.cnblogs.com/lgj-lgj/p/12334912.html