P4742

90分代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define ls id << 1
#define rs id << 1 | 1
#define re register
typedef pair <int,int> pii;
const int MAXN = 1e6 + 10;
int n,m,x,y,head[MAXN],cnt,num[MAXN],ans = -inf,a[MAXN],dp1[MAXN],ans1;
struct Node
{
	int u,v,nxt;
}e[MAXN << 1];
void Add(int u,int v){e[++cnt] = {u,v,head[u]};head[u] = cnt;}
int dfn[MAXN],low[MAXN],timestamp,scc_cnt,id[MAXN],dp[MAXN],din[MAXN],val[MAXN];
stack <int> stk;
bool in_stack[MAXN];
inline void Tarjan(int u)
{
	dfn[u] = low[u] = ++timestamp;
	stk.push(u),in_stack[u] = true;
	for(int i = head[u]; ~ i;i = e[i].nxt)
	{
		int now = e[i].v;
		if(!dfn[now]){Tarjan(now);low[u] = min(low[u],low[now]);}
		else if(in_stack[now]) low[u] = min(low[u],dfn[now]);
	}
	if(dfn[u] == low[u])
	{
		++scc_cnt;int y;
		do
		{
			y = stk.top();stk.pop();
			id[y] = scc_cnt;
			in_stack[y] = false;
		}while(y != u);
	}
}
vector <int> v[MAXN];
signed main()
{
	memset(head,-1,sizeof head);
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= m;i++) cin >> x >> y,Add(x,y);
	for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i);
	for(int i = 1;i <= n;i++) dp1[id[i]] = max(dp1[id[i]],a[i]),val[id[i]] = dp1[id[i]];
	for(int i = 1;i <= n;i++) num[id[i]] += a[i],dp[id[i]] += a[i]; 
	for(int i = 1;i <= n;i++)
		for(int j = head[i]; ~ j;j = e[j].nxt)
		{
			int now = e[j].v;
			if(id[i] != id[now]) v[id[i]].push_back(id[now]),din[now]++;
		}
	for(int i = scc_cnt;i >= 1;i--) ans = max(ans,dp[i]);
	for(int i = scc_cnt;i >= 1;i--)
		for(int j = 0;j < v[i].size();j++)
		{
			int now = v[i][j];
			if(dp[i] + num[now] > dp[now]) 
			{
				dp[now] = dp[i] + num[now];
				dp1[now] = max(dp1[i],val[now]);
			}
			else if(dp[i] + num[now] == dp[now]) dp1[now] = max(dp1[now],dp1[i]);
			if(dp[now] > ans) ans = dp[now],ans1 = dp1[now];
		}
	cout << ans << " " << ans1;
	return 0;
}