为什么我re了QAQ
查看原帖
为什么我re了QAQ
672737
liuguangyuan楼主2022/2/10 18:04

都是runtime error,数组也没开小啊

#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];
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];
stack<int>s;
int cnt,ccnt;
int a[maxn],f[maxn];
void Tarjan(int u)
{
    cnt++;
    dfn[u]=low[u]=cnt;
    s.push(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],low[v]);
        }
        if(dfn[u]==low[u])
        {
            ccnt++;
            int temp;
            do
            {
                temp=s.top();
                s.pop();
                instack[temp]=false;
                belong[temp]=ccnt;
                f[ccnt]+=a[temp];
            }while(temp!=u);
        }
    }

}
int maxx;
bool vis[maxn];
int dis[maxn];
void spfa(int x)
{
    memset(vis,false,sizeof(vis));
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    q.push(x);
    dis[x]=f[x];
    vis[x]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=0;i<G[u].size();i++)
        {
            Edge e=edges[G[u][i]];
            int v=e.to;
            if(dis[v]<dis[u]+f[v])
            {
                dis[v]=dis[u]+f[v];
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    for(int i=1;i<=ccnt;i++)
        maxx=max(maxx,dis[i]);

}
int indegree[maxn];
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);
    }
    init();
    for(int i=0;i<edges.size();i++)
    {
        Edge e=edges[i];
        int x=e.from,y=e.to;
        if(belong[x]!=belong[y])
        {
            add(belong[x],belong[y]);
            indegree[belong[y]]++;
        }
    }
    for(int i=1;i<=ccnt;i++)
    {
        if(indegree[i]==0)
            spfa(i);
    }
    cout<<maxx;
}

2022/2/10 18:04
加载中...