题目链接
思路
考虑到如果一些点两两都能互相到达，那么这些点中，只要有一个点是安全的，就可以顾及到其他所有点，而这些点就是强连通分量（SCC）。
思路很简单，就是每一个强连通分量中的最小值相加得到第一问的解，而第二问就是求每一个强连通分量有几个最小值，相乘得到答案。
代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010,M = 300010,MOD = 1e9 + 7;
int n,m;
int a[N];
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int id[N],scc_cnt,size[N];
int stk[N],top;
bool in_stk[N];
int min_num[N],min_cnt[N];
void add_edge (int a,int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void tarjan (int u) {
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
in_stk[u] = true;
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan (j);
low[u] = min (low[u],low[j]);
}
else if (in_stk[j]) low[u] = min (low[u],dfn[j]);
}
if (dfn[u] == low[u]) {
scc_cnt++;
do {
id[stk[top]] = scc_cnt;
in_stk[stk[top--]] = false;
size[scc_cnt]++;
}
while (stk[top + 1] != u);
}
}
int main () {
memset (h,-1,sizeof (h));
scanf ("%d",&n);
for (int i = 1;i <= n;i++) scanf ("%d",&a[i]);
scanf ("%d",&m);
while (m--) {
int a,b;
scanf ("%d%d",&a,&b);
add_edge (a,b);
}
for (int i = 1;i <= n;i++) {
if (!dfn[i]) tarjan (i);
}
for (int i = 1;i <= scc_cnt;i++) min_num[i] = 2e9;
for (int i = 1;i <= n;i++) {
if (a[i] < min_num[id[i]]) min_num[id[i]] = a[i],min_cnt[id[i]] = 1;
else if (a[i] == min_num[id[i]]) min_cnt[id[i]]++;
}
LL ans1 = 0,ans2 = 1;
for (int i = 1;i <= scc_cnt;i++) ans1 += min_num[i],ans2 = ans2 * min_cnt[i] % MOD;
printf ("%lld %lld\n",ans1,ans2);
return 0;
}