[APIO2018] 铁人两项

标签：APIO2018 int 两项 dcc ++ maxn low cnt 铁人

题意：

问有多少点(x,y,z)满足从x出发经过y到z。且点不能重复经过。

题解：

前置芝士1：

点双有个性质：两点之间简单路径的并集刚好等于这个点双(证明用网络流模型)

等价不同点uv之间一定存在简单路径经过同一个点双内的w。

前置芝士2：

圆方树和点双联系起来，简单地说是对于每一个点双新建一个"方点"，原图的点为圆点。点双内圆点跟对应方点相连

思想有点像tarjan缩点，能方便处理一些仙人掌计数问题(哦其实不是仙人掌也有用)

它长得就很可爱：

 

 第一幅是原图，第二幅在建新点，第三幅就是建完后去掉原图上的边的圆方树了。

圆方树一定是棵树，以及其他性质走这里：【算法学习】圆方树 - 粉兔 - 博客园 (cnblogs.com)

回到这题，建出圆方树后，对于每个圆点赋值-1，方点赋值为点双内圆点数目

两点之间能经过的点数就变成了一路上走过去经过的点权和

转化成了树上求所有路径的权值和

枚举不可能，考虑树dp计算单点贡献，计算有多少路径经过该点即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=4*int(1e5)+5;
int n,m;
struct lys{
    int from,to,nex;
}e[maxn];
int head[maxn],cnt=1;
void add(int from,int to){
    cnt++;e[cnt].to=to;e[cnt].nex=head[from];head[from]=cnt;
}

int dfn[maxn],low[maxn],col[maxn],w[maxn],sz[maxn],timecnt=0;
int dcc_cnt=0,tot=0;
stack<int>s;
vector<int>g[maxn];

void tarjan(int x,int fa){
    tot++;
    dfn[x]=low[x]=++timecnt;
    s.push(x);
    int child=0;
    for(int i=head[x];i;i=e[i].nex){
        int to=e[i].to;
        if(fa==to) continue;
        child++;
        if(!dfn[to]){
            tarjan(to,x);
            low[x]=min(low[x],low[to]);
            if(low[to]>=dfn[x]){
                ++dcc_cnt;
                int p;
                do{
                    p=s.top();s.pop();
                    g[dcc_cnt].push_back(p);
                    g[p].push_back(dcc_cnt);
                    w[dcc_cnt]++;
                }while(p!=to);
                g[dcc_cnt].push_back(x);
                g[x].push_back(dcc_cnt);
                w[dcc_cnt]++;// 注意自己也要加入点双但不退栈(因为一个点可能属于多个点双)
            }
        }
        else low[x]=min(low[x],dfn[to]);
    }
    // 独立点不产生贡献不考虑 
}

long long ans=0;
void dfs(int u,int from){
    sz[u]=(u<=n);
    for(int i=0;i<g[u].size();i++){
        int to=g[u][i];
        if(to==from) continue;
        dfs(to,u);
        ans+=2ll*w[u]*sz[u]*sz[to];
        sz[u]+=sz[to];
        //
    }
    ans+=2ll*w[u]*sz[u]*(tot-sz[u]);
}

int main(){
    cin>>n>>m;
    dcc_cnt=n;
    for(int i=1;i<=n;i++) w[i]=-1;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        add(x,y);add(y,x);
    }
    
    for(int i=1;i<=n;i++)
       if(!dfn[i]){// u still in stack:) 所以要退栈
             tot=0;
             tarjan(i,0);s.pop();
             dfs(i,0);
       }  
    cout<<ans<<endl;
} 

 

标签：APIO2018,int,两项,dcc,++,maxn,low,cnt,铁人
From： https://www.cnblogs.com/liyishui2003/p/17082154.html