初学缩点,60pts求调
查看原帖
初学缩点,60pts求调
327295
GalwayGirl楼主2022/11/8 20:48
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+100,M=1e5+100;
int n,m,w[N],dfn[N],low[N],c,num,stac[N],top,cnt,belong[N],sum[N],head[N],hn[N];
long long max_=-1e18,ans;
bool vis[N];
vector<int>scc[N];
struct xzh{
    int next,to;
}edge[M],en[M];
void add(int u,int v){
    edge[c++].next=head[u];
    edge[c].to=v;
    head[u]=c;
}
void add_scc(int u,int v){
    en[c++].next=hn[u];
    edge[c].to=v;
    hn[u]=c;
}
void tarjan(int now){
    low[now]=dfn[now]=num++;
    stac[top++]=now;vis[now]=true;
    for(int i=head[now];i;i=edge[i].next){
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[now]=min(low[now],low[v]);
        }             
        else if(vis[v])low[now]=min(low[now],low[v]);   
    }
    if(dfn[now]==low[now]){
        cnt++;
        while(1){
            int ls=stac[top];vis[ls]=false;
            belong[ls]=cnt;
            top--;scc[cnt].push_back(ls);
            if(ls==now)break;
        }
    }
}
void dfs(int now){
    vis[now]=true;
    ans+=sum[now];
    for(int i=hn[now];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v])continue;
        dfs(v);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=cnt;i++)
        for(int j=0;j<scc[i].size();j++)
            sum[i]+=w[scc[i][j]];
    c=1;
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=edge[j].next){
            int v=edge[j].to;
            if(belong[i]==belong[v])continue;
            add_scc(belong[i],belong[v]);
        }
    }
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=cnt;i++){
        if(!vis[i])ans=0,dfs(i),max_=max(max_,ans);
    }
    printf("%lld",ans);
    return 0;
}

2022/11/8 20:48
加载中...