题解归档 - cf427C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf427C
• 本地来源：problems/cf427C/idea.md
• 题目链接：https://codeforces.com/contest/427/problem/C
• 原始标题：427C Checkposts

思路

427C Checkposts

题意

有向图 (n) 点 (m) 边，在若干点建检查站（花费 (a_i)）。点 (i) 上的检查站能保护点 (j)，当且仅当 (i=j) 或 (i,j) 在同一 强连通分量（互相可达）。求最小总花费及方案数（每 SCC 恰选一个最小花费点），模 (10^9+7)。

思路

Tarjan 缩点。每个 SCC 内必须且只需建 一个 检查站，选该 SCC 内 (a_i) 最小的点；若最小值有 (k) 个位置，该 SCC 贡献 (k) 种方案。答案为各 SCC 最小花费之和，方案数为各 SCC 最小值个数之积。

复杂度

• 时间：(O(n+m))
• 空间：(O(n+m))

模板

lib/图论(Tarjan-SCC).cpp — 标准 Tarjan，bel[] 为 SCC 编号。

验证

• 样例 ✅
• 对拍 200 组 ✅

结果

• CF #377693405 — AC
• 模板：lib/图论(Tarjan-SCC).cpp

代码

来源：problems/cf427C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:45:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005,mod=1e9+7;
vector<ll>g[maxn];
ll a[maxn+5],dfn[maxn+5],low[maxn+5],ins[maxn+5],bel[maxn+5],stk[maxn+5],n,m,i,u,v,top,tot,scc;
ll ans,ways=1;
void tarjan(ll x){
    dfn[x]=low[x]=++tot;
    stk[++top]=x,ins[x]=1;
    for(lly:g[x]){
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(ins[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        ++scc;
        ll mn=(ll)4e18,cnt=0,zc;
        while(1){
            zc=stk[top--],ins[zc]=0,bel[zc]=scc;
            if(a[zc]<mn) mn=a[zc],cnt=1;
            else if(a[zc]==mn) cnt++;
            if(zc==x) break;
        }
        ans+=mn,ways=(ways*cnt)%mod;
    }
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    while(m--){
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    cout<<ans<<" "<<ways<<"\n";
    return 0;
}