题意：
思路：tarjan缩点后，对新图DAG进行拓扑dp。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
const int inf=1e9+7;
typedef pair<int,int> pll;
int n,m;
int dfn[N], low[N];
int vis[N];
vector<int> ve[N];
int deep=0;
stack<int> s;
int color[N];
int sum=0;
void tarjan(int u) {
dfn[u]=++deep;
low[u]=deep;
vis[u]=1;
s.push(u);
for(int i=0;i<ve[u].size();i++)
{
int v=ve[u][i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else
{
if(vis[v])
{
low[u]=min(low[u],low[v]);
}
}
}
if(dfn[u]==low[u])
{
color[u]=++sum;
// cout<<u<<" "<<sum<<"s\n";
vis[u]=0;
while(s.size()&&s.top()!=u)
{
color[s.top()]=sum;
vis[s.top()]=0;
s.pop();
}
s.pop();
}
}
pll w[N];
int a[N];
vector<int> v2[N];
vector<int> v3[N];
int rd[N];
void init()
{
for(int i=1;i<=n;i++)
{
w[i]={0,0};
v2[i].clear();
ve[i].clear();
v3[i].clear();
vis[i]=0;
dfn[i]=low[i]=0;
}
deep=0;
sum=0;
while(s.size())
{
s.pop();
}
}
void solve()
{
cin>>n>>m;
init();
int x,y,z;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
cin>>x>>y;
ve[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
//cout<<dfn[i]<<" ";
}
for(int i=1;i<=n;i++)
{
w[color[i]].first++;
w[color[i]].second+=a[i];
// cout<<color[i]<<" ";
for(auto v:ve[i])
{
if(color[v]!=color[i])
{
v2[color[i]].push_back(color[v]);
v3[color[v]].push_back(color[i]);
rd[color[v]]++;
}
}
}
int a1=0,a2=0;
queue<int> q;
for(int i=1;i<=sum;i++)
{
if(rd[i]==0)
{
q.push(i);
}
// cout<<w[i].first<<" "<<w[i].second<<" w\n";
}
while(q.size())
{
int w1=q.front();
q.pop();
// cout<<w1<<endl;
for(auto v:v2[w1])
{
rd[v]--;
if(rd[v]==0)
{
q.push(v);
int b1=0,b2=0;
for(int i=0;i<v3[v].size();i++)
{
int ss=v3[v][i];
if(w[ss].first>b1)
{
b1=w[ss].first;
b2=w[ss].second;
}
else if(w[ss].first==b1)
{
b2=min(w[ss].second,b2);
}
}
w[v].first+=b1;
w[v].second+=b2;
}
}
}
for(int i=1;i<=sum;i++)
{
if(w[i].first>a1)
{
a1=w[i].first;
a2=w[i].second;
}
else if(w[i].first==a1)
{
a2=min(w[i].second,a2);
}
}
cout<<a1<<" "<<a2<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}