题解

2 条题解

  • 0
    @ 2022-03-05 13:57:49

    先求出所有割边,那么显然要割掉一条割边。
    如果要加入一条边,那么显然是把若干条割边串起来,使得这些割边不能被割掉。
    那么把割边求出来之后,按照权值从小到大考虑所有割边,第一个不能和前面的构成一条链的割边就是答案。
    那么考虑能否构成一条链。
    首先缩点后形成一棵树,然后维护链的开头、链的结尾,以及链上深度最浅的位置,然后大力讨论一波就好了。讨论的时候仔细一点,不要漏情况。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define MAX 500500
    #define ll long long
    inline int read()
    {
        int x=0;bool t=false;char ch=getchar();
        while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
        if(ch=='-')t=true,ch=getchar();
        while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
        return t?-x:x;
    }
    struct Line{int v,next;}e[MAX<<2];
    int h[MAX],cnt=2,U[MAX<<1],V[MAX<<1],w[MAX<<1];
    inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
    int dfn[MAX],low[MAX],tim;bool ins[MAX],cut[MAX<<1];
    int S[MAX],top,G[MAX],gr;
    void Tarjan(int u,int ff)
    {
        dfn[u]=low[u]=++tim;S[++top]=u;
        for(int i=h[u];i;i=e[i].next)
        {
            int v=e[i].v;if(v==ff)continue;
            if(!dfn[v])
            {
                Tarjan(v,u);
                low[u]=min(low[u],low[v]);
            }
            else low[u]=min(low[u],dfn[v]);
            if(low[v]>dfn[u])cut[i>>1]=true;
        }
        if(dfn[u]==low[u])
        {
            ++gr;int v;
            do{v=S[top--];G[v]=gr;}while(u!=v);
        }
    }
    int fa[MAX],dep[MAX],tp[MAX],hson[MAX],size[MAX];
    void dfs1(int u,int ff)
    {
        fa[u]=ff;dep[u]=dep[ff]+1;size[u]=1;
        for(int i=h[u];i;i=e[i].next)
        {
            int v=e[i].v;if(v==ff)continue;
            dfs1(v,u);size[u]+=size[v];
            if(size[v]>size[hson[u]])hson[u]=v;
        }
    }
    void dfs2(int u,int t)
    {
        tp[u]=t;if(hson[u])dfs2(hson[u],t);
        for(int i=h[u];i;i=e[i].next)
            if(e[i].v!=fa[u]&&e[i].v!=hson[u])
                dfs2(e[i].v,e[i].v);
    }
    int LCA(int u,int v)
    {
        while(tp[u]^tp[v])dep[tp[u]]<dep[tp[v]]?v=fa[tp[v]]:u=fa[tp[u]];
        return dep[u]<dep[v]?u:v;
    }
    int n,m,p[MAX],tot;
    bool cmp(int a,int b){return w[a]<w[b];}
    int main()
    {
        n=read();m=read();
        for(int i=1;i<=m;++i)
            U[i]=read(),V[i]=read(),w[i]=read(),Add(U[i],V[i]),Add(V[i],U[i]);
        Tarjan(1,0);
        for(int i=2;i<cnt;i+=2)if(cut[i>>1])p[++tot]=i>>1;
        sort(&p[1],&p[tot+1],cmp);
        memset(h,0,sizeof(h));cnt=1;
        for(int i=1;i<=m;++i)U[i]=G[U[i]],V[i]=G[V[i]];
        for(int i=1;i<=m;++i)if(U[i]!=V[i])Add(U[i],V[i]),Add(V[i],U[i]);
        dfs1(1,0);dfs2(1,1);
        int H=U[p[1]],T=V[p[1]],M=0;
        if(dep[H]<dep[T])swap(H,T);
        for(int i=2;i<=tot;++i)
        {
            int u=U[p[i]],v=V[p[i]];if(dep[u]<dep[v])swap(u,v);
            int a=LCA(u,H),b=LCA(v,H),c=LCA(u,T),d=LCA(v,T);
            if(!M)
            {
                if(a==u&&b==v&&c==T&&d==T)continue;
                if(a==H&&b==H){H=u;continue;}
                if(c==u&&d==v){T=v;continue;}
                if(c==d&&dep[c]<=dep[T]){T=u;M=v;continue;}
                printf("%d\n",w[p[i]]);return 0;
            }
            else
            {
                if(a==H&&b==H){H=u;continue;}
                if(c==T&&d==T){T=u;continue;}
                if(a==u&&b==v&&c==M&&d==M)continue;
                if(a==M&&b==M&&c==u&&d==v)continue;
                printf("%d\n",w[p[i]]);return 0;
            }
        }
        puts("-1");
        return 0;
    }
    
  • -2
    @ 2017-07-30 14:14:25

    观察:
    1.答案一定是某条边的边权(如果不是-1的话)
    2.答案具有单调性
    因此我们考虑把边权排序后二分答案。
    我们先考虑图是树的情况。
    如果我们选取了边(u,v)的边权作为答案,那么如果我们从图中删除这条边,会形成两个树,分别以u为根和以v为根。如果敌人加入的边不连接两个树,那么(u,v)删除之后仍然会导致图变得不连通,因此我们不妨设敌人加入的边(a,b),a在u子树中,b在v子树中,于是原图形成了一个包含(u,v)的环,于是我们只能选不在环上的边来删除,答案就是不在环上的边的最小值。
    敌人一定会选择让你最小值取到最大的那种情况,类似博弈论。
    观察:
    1.如果(a,b)中a或b不是所在树中的叶子结点,那么将它往下移到叶子结点,会使原来的环包含更多的边,因此敌人一定会选择两个叶子结点相连。
    2.如果两个树中某一个树包含了至少2条不存在祖先后代关系的边权不超过w(u,v)的边,那么敌人加入(a,b)后一定还会剩下这样一条边不在环中,于是我们可以选择这个作为答案,这样保证答案<=我们选取的边权
    因此我们只要二分边权用这个方法判定即可。
    对于图不是树的情况,发现等价于缩点之后的树。
    只要求边双连通分量缩点。

    个人实现的时候在邻接表中记录“桥”(u,v),而对应的反向边(v,u)却不记录,因此找边双连通分量的时候还需要按照dfn序来dfs

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
     
    #define pb push_back
     
    typedef long long ll;
     
    const int inf=0x3f3f3f3f;
    const int N=500000+10;
    const int MOD=338;
    
    int n,m;
    struct edge {
        int to,w;
        bool bridge;
    };
    vector<edge> g[N];
    int low[N];
    int dfn[N],now;
    int bel[N],cnt;
    vector<edge> v[N];
    struct edge2 {
        int x,y,w;
    } e[N];
    int tot;
    int ans=-1;
    void insert(int x,int y,int z) {
        g[x].pb(edge{y,z,0});
        g[y].pb(edge{x,z,0});
    }
    void insert2(int x,int y,int z) {
        e[++tot].x=x,e[tot].y=y,e[tot].w=z;
        v[x].pb(edge{y,z,0});
        v[y].pb(edge{x,z,0});
    }
    void dfs(int x,int fa) {
        dfn[x]=++now;
        int sz=g[x].size();
        low[x]=dfn[x];
        REP(i,0,sz-1) {
            int y=g[x][i].to;
            if (y!=fa) {
                if (dfn[y]==0) {
                    dfs(y,x);
                    low[x]=min(low[x],low[y]);
                    if (low[y]>dfn[x]) {
                        g[x][i].bridge=1;
                    }
                } else low[x]=min(low[x],dfn[y]);
            }
        }
    }
    void merge(int x,int fa,int mark) {
        if (bel[x]) return;
        bel[x]=mark;
        int sz=g[x].size();
        REP(i,0,sz-1) {
            int y=g[x][i].to;
            if (dfn[y]>dfn[x]&&g[x][i].bridge==0&&y!=fa) {
                merge(y,x,mark);
            }
        }
    }
    bool cmp(edge2 a,edge2 b) {
        return a.w<b.w;
    }
    int dfs2(int x,int fa,int ban,int val) {
        int sz=v[x].size();
        int res=0;
        REP(i,0,sz-1) {
            int y=v[x][i].to;
            int t=0;
            if (y!=fa&&y!=ban) {
                t=dfs2(y,x,ban,val);
                if (t==0) {
                    if (v[x][i].w<=val) t=1;
                }
                res+=t;
            }
        }
        return res;
    }
    bool check(int x) {
        int val=e[x].w;
        int u=e[x].x,v=e[x].y;
        //cout<<u<<" "<<v<<endl;
        int res=0,res2=0;
        res=dfs2(u,0,v,val);
        res2=dfs2(v,0,u,val);
        if (res>=2||res2>=2) return 1;
        else return 0;
    }
    int main() {
        cin>>n>>m;
        FOR(i,m) {
            int x,y,z;
            cin>>x>>y>>z;
            insert(x,y,z);
        }
        dfs(1,0);
        FOR(i,n) if (!bel[i]) merge(i,0,++cnt);
        FOR(i,n) {
            int sz=g[i].size();
            REP(j,0,sz-1) {
                if (g[i][j].bridge) {
                    insert2(bel[i],bel[g[i][j].to],g[i][j].w);
                }
            }
        }
        sort(e+1,e+1+tot,cmp);
        //FOR(i,tot) {
        //  cout<<i<<":"<<e[i].x<<" "<<e[i].y<<" "<<e[i].w<<endl;
        //}
        int l=1,r=tot;
        int mid=0;
        while (l<=r) {
            mid=(l+r)>>1;
            if (check(mid)) {
                ans=e[mid].w;
                r=mid-1;
            } else l=mid+1;
        }
        cout<<ans<<endl;
        return 0;
    }
    
  • 1

信息

ID
1954
难度
8
分类
(无)
标签
递交数
136
已通过
13
通过率
10%
被复制
3
上传者