BZOJ1123: [POI2008]BLO【Tarjan】

1123: [POI2008]BLO

【题目描述】

传送门

【题解】

这题就是求割点周围的连通块大小,然后乘一下就可以了,不是割点的点答案肯定是2*(n-1)。

代码如下

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5,MAXE=5e5+5;
typedef long long LL;
int n,m,Root,tim,Siz[MAXN],Dfn[MAXN],Low[MAXN];
bool cur[MAXN];
vector<int> G[MAXN];
struct Edge{
    int tot,lnk[MAXN],son[MAXE<<1],nxt[MAXE<<1];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
void Tarjan(int x){
    int Child=0,Now=0;Dfn[x]=Low[x]=++tim;Siz[x]=1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(!Dfn[E.son[j]]){
        Child++;Tarjan(E.son[j]),Siz[x]+=Siz[E.son[j]],Low[x]=min(Low[x],Low[E.son[j]]);
        if((x==Root&&Child>1)||(x!=Root&&Dfn[x]<=Low[E.son[j]])) cur[x]=1,G[x].push_back(Siz[E.son[j]]),Now+=Siz[E.son[j]];
    }else Low[x]=min(Low[x],Dfn[E.son[j]]);
    if(cur[x]) G[x].push_back(n-Now-1);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1,x,y;i<=m;i++) x=read(),y=read(),E.Add(x,y),E.Add(y,x);
    for(int i=1;i<=n;i++) if(!Dfn[i]) Tarjan(Root=i);
    for(int i=1;i<=n;i++){
        LL Ans=2*n-2;
        for(int j=0,END=G[i].size();j<END;j++)
        for(int k=j+1;k<END;k++) Ans+=(LL)2*(LL)G[i][j]*G[i][k];
        printf("%lld\n",Ans);
    }
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部