P4630 [APIO2018] Duathlon 铁人两项

不念不忘少年蓝@ 2021-12-23 14:01 122阅读 0赞

### 思路 ###

圆方树，一个点双中的所有点都可以被经过，所以给圆点赋值-1，方点赋值为圆点个数，统计圆点两两之间的路径权值和即可

### 代码 ###

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <stack>
    using namespace std;
    int v2[100100*4],fir2[100100*2],nxt2[100100*4],cnt2;
    void addedge2(int ui,int vi){
        ++cnt2;
        v2[cnt2]=vi;
        nxt2[cnt2]=fir2[ui];
        fir2[ui]=cnt2;
    }
    int v[100100*4],fir[100100*2],nxt[100100*4],cnt;
    void addedge(int ui,int vi){
        ++cnt;
        v[cnt]=vi;
        nxt[cnt]=fir[ui];
        fir[ui]=cnt;
    }
    int fd_cnt,dfn[100100*2],low[100100*2],w_p[100100*2],dfs_clock;
    int S[100100*2],topx=0,n,m,num;
    void dfs(int u){
        low[u]=dfn[u]=++dfs_clock;
        S[++topx]=u;
        num++;
        for(int i=fir[u];i;i=nxt[i]){
            if(!dfn[v[i]]){
                dfs(v[i]);
                low[u]=min(low[u],low[v[i]]);
                if(low[v[i]]==dfn[u]){
                    ++fd_cnt;
                    w_p[fd_cnt]=0;
                    for(int x=0;x!=v[i];topx--){
                        x=S[topx];
                        addedge2(fd_cnt,x);
                        addedge2(x,fd_cnt);
                        ++w_p[fd_cnt];
                    }
                    addedge2(u,fd_cnt);
                    addedge2(fd_cnt,u);
                    ++w_p[fd_cnt];    
                }
            }
            else
                low[u]=min(low[u],dfn[v[i]]);
        }
    }
    int sz[100100*2];
    long long ans;
    void dfs(int u,int f){
        sz[u]=(u<=n);
        for(int i=fir2[u];i;i=nxt2[i]){
            if(v2[i]==f)
                continue;
            dfs(v2[i],u);
            ans+=2LL*w_p[u]*sz[u]*sz[v2[i]];
            sz[u]+=sz[v2[i]];
        }
        ans+=2LL*w_p[u]*sz[u]*(num-sz[u]);    
    }
    int main(){
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
            w_p[i]=-1;
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            addedge(a,b);
            addedge(b,a);
        }
        fd_cnt=n;
        for(int i=1;i<=n;i++)
            if(!dfn[i]){
                num=0;
                dfs(i);
                topx--;
                dfs(i,0);
            }
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/dreagonm/p/10766117.html