求大佬帮忙
查看原帖
求大佬帮忙
648660
Name1楼主2022/7/15 12:34

莫名其妙40分,大佬能帮忙看看吗。

#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#define time time1
using namespace std;
const int N=1e4+1e5,M=1e5+1e4;
int n,m,a[N];
int cnt,head[N];
struct Edge{int next,u,v,w;}e[M];
inline void add(int u,int v,int w)
{
	e[++cnt]=(Edge){head[u],u,v,w};
	head[u]=cnt;
}
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
int dfn[N],low[N],time1,in_s[N],scc[N],sc,sz[N];
stack<int> s;
inline void tarjan(int u)
{
	s.push(u);
	dfn[u]=low[u]=++time,in_s[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(!dfn[v]) 
		{
			tarjan(v);
			low[u]=min(low[v],low[u]);
		}
		else if(in_s[v]) low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u])
	{
		sc++;
		while(!s.empty())
		{
			in_s[s.top()]=1;
			scc[s.top()]=sc;
			sz[sc]+=a[s.top()];
			s.pop();
		}
	}
}
vector<int> E[N];
int vis[N],ans;
inline void DP(int u)
{
	if(vis[u]) return;
	vis[u]=sz[u];
	int sum=0;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(!vis[v]) DP(v);
		sum=max(sum,vis[v]);
	}
	vis[u]+=sum;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	while(m--)
	{
		int u=read(),v=read();
		add(u,v,1);
	}
	for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);
	for(int i=1;i<=m;i++)
	{
		if(scc[e[i].u]!=scc[e[i].v])
			E[scc[e[i].u]].push_back(scc[e[i].v]);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]) DP(i);
		ans=max(ans,vis[i]);
	}
	printf("%d",ans);
	return 0;
}
2022/7/15 12:34
加载中...