洛谷P4630/APIO2018 Duathlon 铁人两项

@Pelom  November 1, 2019

题意

无向图中,求三元组$(s,c,f)$的个数,使得从$s \rightarrow v \rightarrow f$为简单路径

数据范围:$n \le 100000,m \le 200000$

题解

可以发现,答案就是路径上可能经过的点数
将图缩成圆方树,统计树上路径点数
若将方点点权标为点双大小,圆点点权标为$-1$,则某条路径上的答案就是圆方树上两点之间的点权和
因为枚举点对是$O(n^2)$的,所以改为统计每个点被经过多少次,再乘上它的权值,复杂度为$O(n)$

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=200000+10;
int n,m,u,v;
int dep,tot,top,cnt;
LL ans;
int dfn[N],low[N],stk[N],siz[N<<1],w[N<<1];
LL sum[N<<1];
struct edge{
    int nxt,to;
};
struct graph{
    int cnt;
    int head[N];
    edge e[N<<2];
    inline void add(int u,int v){
        e[++cnt]=edge{head[u],v};
        head[u]=cnt;
    }
} g1,g2;
void Tarjan(int u,int f){
    dfn[u]=low[u]=++dep;
    stk[++top]=u;
    w[u]=-1;
    cnt++;
    for(int i=g1.head[u];i;i=g1.e[i].nxt){
        int v=g1.e[i].to;
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                tot++;
                g2.add(tot,u);
                g2.add(u,tot);
                w[tot]=1;
                for(int t=0;t!=v;){
                    t=stk[top--];
                    g2.add(tot,t);
                    g2.add(t,tot);
                    w[tot]++;
                }
            }
        }
        else if(v!=f)
            low[u]=min(low[u],dfn[v]);
    }
}
void dfs(int u,int f){
    siz[u]=(u<=n);
    LL sum=0;
    for(int i=g2.head[u];i;i=g2.e[i].nxt){
        int v=g2.e[i].to;
        if(v==f)
            continue;
        dfs(v,u);
        sum+=2ll*siz[u]*siz[v];
        siz[u]+=siz[v];
    }
    sum+=2ll*siz[u]*(cnt-siz[u]);
    ans+=sum*w[u];
}
int main(){
    scanf("%d%d",&n,&m);
    tot=n;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        g1.add(u,v);
        g1.add(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]){
            cnt=0;
            Tarjan(i,0);
            dfs(i,0);
        }
    printf("%lld",ans);
    return 0;
}

添加新评论