题目链接

• 题意：
  
  给定n个点，每一个点有一个权值的有向图。如今须要选定一些点，使得这些点权值和最小。且满足：假设i能到达j且j能到达i，那么i、j能够仅仅选一个
• 分析：
  
  强联通模板题

//使用时仅仅更新G完毕构图

//scc_cnt从1開始计数

//pre[]表示点在DFS树中的先序时间戳

//lowlink[]表示当前点和后代能追溯到的最早祖先的pre值

//sccno[]表示点所在的双连通分量编号

//vector<int> G保存每一个点相邻的下一个点序号

//stack<Edge> S是算法用到的栈

const int MAXV = 310000;

vector<int> G[MAXV];

int pre[MAXV], lowlink[MAXV], sccno[MAXV], dfs_clock, scc_cnt;

stack<int> S;

void init(int n)

{

    REP(i, n) G[i].clear();

}

void dfs(int u)

{

    pre[u] = lowlink[u] = ++dfs_clock;

    S.push(u);

    for(int i = 0; i < G[u].size(); i++)

    {

        int v = G[u][i];

        if(!pre[v])

        {

            dfs(v);

            lowlink[u] = min(lowlink[u], lowlink[v]);

        }

        else if(!sccno[v])

        {

            lowlink[u] = min(lowlink[u], pre[v]);

        }

    }

    if(lowlink[u] == pre[u])

    {

        scc_cnt++;

        for(;;)

        {

            int x = S.top();

            S.pop();

            sccno[x] = scc_cnt;

            if(x == u) break;

        }

    }

}

void find_scc(int n)

{

    dfs_clock = scc_cnt = 0;

    memset(sccno, 0, sizeof(sccno));

    memset(pre, 0, sizeof(pre));

    for(int i = 0; i < n; i++)

        if(!pre[i]) dfs(i);

};

int cost[MAXV];

vector<int> vt[MAXV];

int Min[MAXV];

int main()

{

//    freopen("in.txt", "r", stdin);

    int n, e, a, b;

    while (~RI(n))

    {

        init(n);

        REP(i, MAXV) vt[i].clear();

        CLR(Min, INF);

        REP(i, n) RI(cost[i]);

        RI(e);

        REP(i, e)

        {

            RII(a, b); a--; b--;

            G[a].push_back(b);

        }

        find_scc(n);

        REP(i, n)

        {

            int no = sccno[i];

            vt[no].push_back(i);

            Min[no] = min(Min[no], cost[i]);

        }

        LL v = 0, ans = 1;

        REP(i, MAXV)

        {

            if (vt[i].size() > 0)

            {

                int cnt = 0;

                REP(j, vt[i].size())

                {

                    if (cost[vt[i][j]] == Min[i]) cnt++;

                }

                ans *= cnt;

                ans %= MOD;

                v += Min[i];

            }

        }

        cout << v << ' ' << ans << endl;

    }

    return 0;

}