萌新求助一道题QAQ
  • 板块学术版
  • 楼主liuguangyuan
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/3/20 15:46
  • 上次更新2023/10/28 06:05:34
查看原帖
萌新求助一道题QAQ
672737
liuguangyuan楼主2022/3/20 15:46

这是我的代码,为什么会RE啊,数组开的1e6

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m;
struct Edge
{
    int from,to;
};
vector<Edge>edges;
vector<int>G[maxn];
vector<int>V[maxn];
void init()
{
    for(int i=1;i<=n;i++)
        G[i].clear();
    edges.clear();
}
void add(int from,int to)
{
    edges.push_back({from,to});
    int m=edges.size();
    G[from].push_back(m-1);
}

int dfn[maxn],low[maxn],belong[maxn];
bool instack[maxn];
int s[maxn];
int cnt,ccnt;
int a[maxn],f[maxn];
int index_;
void Tarjan(int u)
{
    cnt++;
    dfn[u]=low[u]=cnt;
    s[index_++]=u;
    instack[u]=true;
    for(int i=0;i<G[u].size();i++)
    {
        Edge e=edges[G[u][i]];
        int v=e.to;
        if(!dfn[v])
        {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u])
        {
            ccnt++;
            int temp;
            index_--;
            do
            {
                temp=s[index_];
                index_--;
                instack[temp]=false;
                belong[temp]=ccnt;
                f[ccnt]+=a[temp];
            }while(temp!=u);
        }
    }

}
int maxx;
bool vis[maxn];
int dis[maxn];
int indegree[maxn];
int topsort()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    for(int i=1;i<=ccnt;i++)
    {
        if(indegree[i]==0)
            q.push(i);
        dis[i]=f[i];
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<V[u].size();i++)
        {
            int v=V[u][i];
            dis[v]=max(dis[v],dis[u]+f[v]);
            indegree[v]--;
            if(indegree[v]==0)
                q.push(v);
        }
    }
    int ans=0;
    for(int i=1;i<=ccnt;i++)
    {
        ans=max(ans,dis[i]);
    }
    return ans;


}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            Tarjan(i);
    }

    for(int i=0;i<edges.size();i++)
    {
        Edge e=edges[i];
        int x=e.from,y=e.to;
        if(belong[x]!=belong[y])
        {
            V[belong[x]].push_back(belong[y]);
            indegree[belong[y]]++;
        }
    }
   cout<<topsort();
}

2022/3/20 15:46
加载中...