lessons/参考实现/02-强连通与双连通/CodeForces-427C.cpp

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> cost(n);
    for (auto &x : cost) cin >> x;
    int m;
    cin >> m;
    vector<vector<int>> g(n);
    while (m--) {
        int u, v; cin >> u >> v;
        g[--u].push_back(--v);
    }

    vector<int> dfn(n), low(n), comp(n, -1), st;
    vector<bool> in_stack(n, false);
    int timer = 0, components = 0;
    auto dfs = [&](auto &&self, int u) -> void {
        dfn[u] = low[u] = ++timer;
        st.push_back(u); in_stack[u] = true;
        for (int v : g[u]) {
            if (!dfn[v]) { self(self, v); low[u] = min(low[u], low[v]); }
            else if (in_stack[v]) low[u] = min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u]) {
            while (true) {
                int v = st.back(); st.pop_back(); in_stack[v] = false;
                comp[v] = components;
                if (v == u) break;
            }
            ++components;
        }
    };
    for (int v = 0; v < n; ++v) if (!dfn[v]) dfs(dfs, v);

    vector<long long> best(components, LLONG_MAX), ways(components, 0);
    for (int v = 0; v < n; ++v) {
        int c = comp[v];
        if (cost[v] < best[c]) best[c] = cost[v], ways[c] = 1;
        else if (cost[v] == best[c]) ++ways[c];
    }
    constexpr long long mod = 1'000'000'007LL;
    long long answer_cost = 0, answer_ways = 1;
    for (int c = 0; c < components; ++c) {
        answer_cost += best[c];
        answer_ways = answer_ways * ways[c] % mod;
    }
    cout << answer_cost << ' ' << answer_ways << '\n';
}