Codeforces Round #244 (Div. 2)??Checkposts_html/css_WEB-ITnose-html教程-PHP中文网

题目链接

题意：
给定n个点，每个点有一个权值的有向图。现在需要选定一些点，使得这些点权值和最小，且满足：如果i能到达j且j能到达i，那么i、j可以只选一个

分析：
强联通模板题

Interior AI

AI室内设计，上传室内照片自动帮你生成多种风格的室内设计图

下载

//使用时只更新G完成构图//scc_cnt从1开始计数//pre[]表示点在DFS树中的先序时间戳//lowlink[]表示当前点和后代能追溯到的最早祖先的pre值//sccno[]表示点所在的双连通分量编号//vector G保存每个点相邻的下一个点序号//stack S是算法用到的栈const int MAXV = 310000;vector G[MAXV];int pre[MAXV], lowlink[MAXV], sccno[MAXV], dfs_clock, scc_cnt;stack 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 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;}