tarjan+拓扑 40pts

#include<queue>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
int n,m,top=0,tot=0,tim;
const int maxn = 1e5 + 10;
int val[maxn];
struct node{
	int next;
	int to;
	int from;
}g[maxn],e[maxn];
bool vis[maxn],c;
int low[maxn],dfn[maxn],stack[maxn],h[maxn],head[maxn];
int val2[maxn];
int in[maxn],dit[maxn];
void add(int x,int y){
	e[++tot].to = y;
	e[tot].from = x;
	e[tot].next = head[x];
	head[x] = tot;
}
void dfs(int k) {
	dfn[k]=low[k]=++tim;
	vis[k]=true;
	stack[++top]=k;
	for(int i=head[k]; i; i=e[i].next) {
		int v=e[i].to;
		if(!dfn[v]) {
			dfs(v);
			low[k]=min(low[k],low[v]);
		} else if(vis[v]) {
			low[k]=min(low[k],dfn[v]);
		}
	}
	if(dfn[k]==low[k]) {
		int y;
		while(y=stack[top--]) {
			val2[y]=k;
			vis[y]=false;
			if(k==y) break;
			val[k]+=val[y];
		}
	}
}
int work() {
	queue<int> q;
	for(int i=1; i<=n; i++) {
		if(val2[i]==i&&in[i]==0) {
			q.push(i);
			dit[i]=val[i];
		}
	}
	while(!q.empty()) {
		int k=q.front();
		q.pop();
		for(int i=h[k];i;i=g[i].next) {
			int v=g[i].to;
			dit[v]=max(dit[v],dit[k]+val[v]);
			in[v]--;
			if(in[v]==0) q.push(v);
			
		}
	}
	int ans=-1;
	for(int i=1; i<=n; i++) {
		ans=max(ans,dit[i]);
	}
	return ans;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&val[i]);
	for(int i=1; i<=m; i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y); 
	}
	for(int i=1; i<=n; i++) {
		if(!dfn[i]) dfs(i);
	}
	for(int i=1; i<=m; i++) {
		int x=val2[e[i].from],y=val2[e[i].to];
		if(x!=y) {
			g[++c].to = y;
			g[c].next = h[x];
			g[c].from = x;
			h[x] = c;
			in[y]++;
		}
	}
	printf("%d",work());
	return 0;
}

1 WA

3 4 5 7 9 TLE

帮蒟蒻看看吧/kk