TLE什么鬼
查看原帖
TLE什么鬼
131610
luo_shen楼主2021/1/9 20:13

求大佬帮助,10TLE

using namespace std;
const int MAX=2147483647;
int n,m,tmp,top,tot,color_num;
int dfn[10010],low[10010],d[10010],head[10010],_stack[10010];
int color[10010],sum[10010],rd[10010],dp[10010];
bool in_stack[10010];
struct node{
    int u,v,next;
}e[100100],_map[100100];
int read(){
    int f=1,s=0;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-'){
            f=-1;
        }
    }
    while(ch<='9'&&ch>='0'){
        s=s*10+(ch-'0');
        ch=getchar();
    }
    return f*s;
}
void add(int u,int v){
    ++tot;
    e[tot].u=u;
    e[tot].v=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void tarjan(int u){
    low[u]=dfn[u]=++tmp;
    in_stack[u]=true;
    _stack[++top]=u;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        sum[++color_num]+=d[u];
        color[u]=color_num;
        in_stack[u]=false;
        while(_stack[top]!=u){
            int v=_stack[top];
            color[v]=color_num;
            sum[color_num]+=d[v];
            in_stack[v]=false;
            top--;
        }
        top--;
    }
}
void add1(int u,int v){
    _map[++tot].u=u;
    _map[tot].v=v;
    _map[tot].next=head[u];
    head[u]=tot;
}
void DAG(){
    queue<int>q;
    for(int i=1;i<=color_num;i++){
        if(!rd[i]){
            q.push(i);
            dp[i]=sum[i];
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=_map[i].next){
            int v=_map[i].v;
            dp[v]=max(dp[u]+sum[v],dp[v]);
            rd[v]--;
            if(!rd[v]){
                q.push(v);
            }
        }
    }
}
int main(){
    int x,y;
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        d[i]=read();
    }
    for(int i=1;i<=m;i++){
        x=read(),y=read();
        add(x,y);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    memset(head,0,sizeof(head));
    tot=0;
    for(int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v;
        if(color[u]!=color[v]){
            add1(color[u],color[v]);
            rd[color[v]]++;
        }
    }
    DAG();
    int mx=0;
    for(int i=1;i<=color_num;i++){
        mx=max(mx,dp[i]);
    }
    cout<<mx<<endl;
    return 0;
}```
2021/1/9 20:13
加载中...