RT，WA #1 #3 #4 #5 #7 #9 qwq

Record

Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+1;
const int maxm=1e5+1;
const int inf=0x3f3f3f3f;
struct edge{
	int from,to,next;
}e0[maxm],e1[maxm];
int n,m,ans,tot0,tot1,cnt,h0[maxn],h1[maxn],in[maxn],d[maxn],siz[maxn];
int a[maxn],tim,dfn[maxn],low[maxn],vis[maxn],state[maxn];
stack <int> st;
queue <int> q;
inline void addEdge0(int x,int y){
	e0[++tot0]=(edge){x,y,h0[x]};
	h0[x]=tot0;
}
inline void addEdge1(int x,int y){
	e1[++tot1]=(edge){x,y,h1[x]};
	h1[x]=tot1;
	in[y]++;
}
inline void dfs(int x){
	dfn[x]=low[x]=++tim;
	st.push(x);
	vis[x]=1;
	for (int i=h0[x];i;i=e0[i].next){
		int v=e0[i].to;
		if (!vis[v]){
			dfs(v);
			low[x]=min(low[x],low[v]);
		}else if (vis[v]==1) low[x]=min(low[x],dfn[v]);
	}
	if (low[x]==dfn[x]){
		cnt++;
		while (!st.empty()){
			state[st.top()]=cnt;
			siz[cnt]+=a[st.top()];
			st.pop();
		}
	}
}
inline void topo(){
	for (int i=1;i<=cnt;i++){
		if (!in[i]){
			d[i]=siz[i];
			q.push(i);
		}
	}
	while (!q.empty()){
		int now=q.front();
		q.pop();
		for (int i=h1[now];i;i=e1[i].next){
			int v=e1[i].to;
			d[v]=max(d[v],d[now]+siz[v]);
			if (!--in[v]) q.push(v);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		addEdge0(u,v);
	}
	for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
	for (int i=1;i<=tot0;i++){
		int u=e0[i].from,v=e0[i].to;
		if (state[u]!=state[v]) addEdge1(state[u],state[v]);
	}
	topo();
	for (int i=1;i<=cnt;i++) ans=max(ans,d[i]);
	printf("%d\n",ans);
	return 0;
}

悬赏一个关注