P5234 [JSOI2012]越狱老虎桥 题解

· · 题解

前言:好多题解被 hack 了啊。

Problem

题目大意：给定一张图，A 先添加 1 条边，B 再删去一条边使得图不连通，A 要最大化删除边的权值，B 要最小化删除边的权值，问最终的权值是多少。

数据范围： n \leq 5 \times 10^5,m \leq 10^6。

Solution

前置芝士：边双连通分量。

显然，边双中的边是肯定不能删的，因为删除了也并不会使图不连通。所以我们有个自然的想法，我们可以把边双缩点，在重新建图，这样我们就简化为了树上问题。

然后我们考虑树上怎么做，想一想会发现，A 的操作链接 i,j 等价于将树上 i,j 缩点之后的编号 i',j' 链上的边去掉了，因为加边后这条链会构成一个边双，删除边双中的任意一个点都是无法使图不连通的，这个很显然。

然后我们可以考虑，从小到大枚举每一条边，看看枚举的这条边和之前的边能否构成一条链，如果不能构成那么显然这条边就是答案，否则若所有边都可以构成一条链，那么输出 -1 即可。

至于如何判断能否构成链，可以发现，我们以最小的边的任意一个端点作为根节点，那么除了根节点，显然每一个点只能有一个点作为它的儿子，若新加边的端点往上跳，若跳到一个点有儿子且不是自己，那么就够不成链。根节点要特判一下。

至于时间复杂度，本来我想用倍增的，但是我们可以发现，每一个点只会被更新一次，更新第二次要么直接退出（即发现构不成链），或者不用往上跳了（显然，当前节点满足，祖先节点显然不影响）。所以暴力跳是均摊的复杂度，是比非均摊的倍增还快的。

结合代码感性理解一下哈！

截止 2023.2.9，暂时过了所有 hack。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7232;
int n,m,x,y,z;
struct hl{
    int v,nxt,w;
}e[N];
struct len{
    int u,v,w;
}t[N];
int h[N],cnt=1;
bitset<N> vis;
void add(int u,int v,int w)
{
    e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;e[cnt].w=w;
}
int mi(int x,int y){return x<y?x:y;}
int dfn[N],low[N],tot,now;
void tarjan(int x,int fx)
{
    dfn[x]=low[x]=++tot;
    for(int i=h[x];i;i=e[i].nxt)
    {
        if(e[i].v==fx) continue;
        if(!dfn[e[i].v])
        {
            tarjan(e[i].v,x);
            low[x]=mi(low[x],low[e[i].v]);
            if(low[e[i].v]>dfn[x]) vis[i]=vis[i^1]=1;
        }
        else low[x]=mi(low[x],dfn[e[i].v]);
    }
}
int ecc[N];
void dfs(int x)
{
    ecc[x]=now;
    for(int i=h[x];i;i=e[i].nxt)
    {
        if(vis[i]||ecc[e[i].v]) continue;
        dfs(e[i].v);
    }
}
bool cmp(len x,len y)
{
    return x.w<y.w;
}
int fa[N],dis[N],dep[N],son;
void dfss(int x,int fx)
{
    fa[x]=fx;dep[x]=dep[fx]+1;
    for(int i=h[x];i;i=e[i].nxt)
    {
        if(e[i].v==fx) continue;
        dfss(e[i].v,x);
    }
}
int num;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
        t[i]={x,y,z};
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
    for(int i=1;i<=n;i++) if(!ecc[i]) ++now,dfs(i);//找边双
    memset(h,0,sizeof(h));cnt=0;
    for(int i=1;i<=m;i++)
        if(ecc[t[i].u]!=ecc[t[i].v]) add(ecc[t[i].u],ecc[t[i].v],t[i].w),add(ecc[t[i].v],ecc[t[i].u],t[i].w),t[++num]=t[i];
    //重新加边
    sort(t+1,t+num+1,cmp);
    dfss(ecc[t[1].u],0);dis[ecc[t[1].u]]=ecc[t[1].v];//以最小的边的一个端点作为根
    for(int i=2;i<=num;i++)
    {
        int k=dep[ecc[t[i].u]]>dep[ecc[t[i].v]]?ecc[t[i].u]:ecc[t[i].v];//从深度深的跳
        while(!dis[fa[k]]) dis[fa[k]]=k,k=fa[k];//跳到一个固定儿子的点
        if(son==0&&fa[k]==ecc[t[1].u]&&dis[fa[k]]!=k) son=k;//若为根，特判
        else if(dis[fa[k]]==k||fa[k]==ecc[t[1].u]&&son==k) ;//若当前节点的父亲在链上的儿子就是自己，那么退出
        else //否则输出边的权值
        {
            printf("%d\n",t[i].w);
            return 0;
        }
    }
    printf("-1\n");
}