萌新刚学OI,RE求助
查看原帖
萌新刚学OI,RE求助
113073
EricQian楼主2020/8/13 20:40

各位巨佬能帮忙看看吗?

测评记录

#include<bits/stdc++.h>
using namespace std;
#define Maxn 10005
#define Maxm 100005
#define inf 0x3f3f3f3f
int n,m,sum,Time;
int a[Maxn],sumkuai[Maxn],ds[Maxn],ind[Maxn];
int dfn[Maxn],low[Maxn],belong[Maxn];
int tot,hea[Maxn],ver[Maxm],fro[Maxm],nex[Maxm];
stack<int> s;
vector<int> g[Maxn];
bool ins[Maxn]={false};
inline void add(int x,int y)
{
     ver[++tot]=y,fro[tot]=x,nex[tot]=hea[x],hea[x]=tot;
}
void tarjan(int x)
{
     dfn[x]=low[x]=++Time;
     s.push(x),ins[x]=true;
     for(int i=hea[x];i;i=nex[i])
     {
         if(!dfn[ver[i]]) tarjan(ver[i]),low[x]=min(low[ver[i]],low[x]);
         else if(ins[ver[i]]) low[x]=min(dfn[ver[i]],low[x]);
     }
     if(dfn[x]==low[x])
     {
         sum+=1;
         do
         {
             belong[x]=sum;
             sumkuai[sum]+=a[x];
             x=s.top(),s.pop();
             ins[x]=false;
         } while(dfn[x]!=low[x]);
     }
}
int topo()
{
	 queue<int> q;
     for(int i=1;i<=sum;i++) if(!ind[i]) ds[i]=sumkuai[i],q.push(i);
     while(!q.empty())
     {
         int cur=q.front();
         q.pop();
         for(int i=0;i<g[cur].size();i++)
         {
         	 int v=g[cur][i];
             ind[v]-=1;
             ds[v]=max(ds[v],ds[cur]+sumkuai[v]);
             if(!ind[v]) q.push(v);
         }
    }
     int MAX=-1;
     for(int i=1;i<=sum;i++) MAX=max(MAX,ds[i]);
     printf("%d\n",MAX);
}
int main()
{
     //freopen(".in","r",stdin);
     //freopen(".out","w",stdout);
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
     int u,v;
     for(int i=1;i<=m;i++) scanf("%d%d",&u,&v),add(u,v);
     for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
     for(int i=1;i<=tot;i++)
         if(belong[fro[i]]!=belong[ver[i]]) g[belong[fro[i]]].push_back(belong[ver[i]]),ind[belong[ver[i]]]++;
     topo();
     //fclose(stdin);
     //fclose(stdout);
     return 0;
}
2020/8/13 20:40
加载中...