求调
查看原帖
求调
575066
ALL_FallsDown楼主2024/10/11 22:25

第一眼看到这道题给看傻了,自己都不知道自己在写什么

#include<bits/stdc++.h>
using namespace std;
int n,m,head[100005],ver[100005],nex[100005],cnt,u[1000005],v[1000005];
void add(int x,int y){
    cnt++;
    nex[cnt]=head[x];
    ver[cnt]=y;
    head[x]=cnt;
}
int dfn[100005],low[100005],num,vis[100005],s[1000005],p[100005],top,tot,sum[100005];
void tarjan(int x){
    dfn[x]=low[x]=++num;
    vis[x]=1;
    s[++top]=x;
    for(int i=head[x];i;i=nex[i]){
        if(dfn[ver[i]]==0){
            tarjan(ver[i]);
            low[x]=min(low[x],low[ver[i]]);
        }
        else if(vis[ver[i]]!=0){
            low[x]=min(low[x],dfn[ver[i]]);
        }
    }
    if(dfn[x]==low[x]){
        tot++;
        int y;
        do{
            y=s[top--];
            vis[y]=0;
            p[y]=tot;
        }while(x!=y);
    }
}
int edg[100005],d[100005],q[100005];
int h[100005],ve[100005],ne[100005],cntt;
void addd(int x,int y){
    cntt++;
    ne[cntt]=h[x];
    ve[cntt]=y;
    h[x]=cntt;
}
int dis[100005],vi[100005],maxx,numm;
void findd(int x){
    vi[x]=1;
    if(maxx<dis[x]) maxx=dis[x];
    for(int i=h[x];i;i=ne[i]){
        if(vi[ve[i]]) continue;
        if(dis[ve[i]]<dis[x]+sum[ve[i]]) dis[ve[i]]=dis[x]+sum[ve[i]];
        findd(ve[i]);
    }
}
int f[100005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>edg[i];
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        add(u[i],v[i]);
    }
    for(int j=1;j<=n;j++){
        if(dfn[j]==0) tarjan(j);
    }
    for(int i=1;i<=n;i++){
        if(q[p[i]]==0){
            numm++;
            d[p[i]]=n+numm;
            q[p[i]]=1;
        }
        sum[d[p[i]]]+=edg[i];
    }
    for(int j=1;j<=m;j++){
        addd(d[p[u[j]]],d[p[v[j]]]);
    }
    for(int j=1;j<=n;j++){
        memset(vi,0,sizeof(vi));
        memset(dis,0,sizeof(dis));
        dis[d[p[j]]]=sum[d[p[j]]];
        findd(d[p[j]]);
    }
    cout<<maxx;
    return 0;
}
2024/10/11 22:25
加载中...