Codeforces Round #244 (Div. 2) C. Checkposts

裸的tarjan

依题意有向图上i和j之间能互相到达，i和j肯定在同一个scc内

最小的代价就是Σ每个scc内最小的cost

方案就是每个scc内最小值的数的乘积

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
const int maxn=int(1e5)+7;
int n,m,s,num=0,step=0,Scc=0,dp[maxn],rd[maxn],weight[maxn],scc[maxn],dfn[maxn],flag[maxn],low[maxn],stap[maxn];
long long minscc[maxn],p[maxn],w[maxn];
struct lys{
    int from,to,next;
}e[maxn*7];
int cnt=0,head[maxn*7];
void add(int from,int to){
    cnt++;e[cnt].from=from;e[cnt].to=to;e[cnt].next=head[from];head[from]=cnt;
}
struct lys2{
    int from,to,next;
}e2[maxn*7];
int cnt2=0,head2[maxn*7];
void add2(int from,int to){
    cnt2++;e2[cnt2].from=from;e2[cnt2].to=to;e2[cnt2].next=head2[from];head2[from]=cnt2;
}
void init(){
    memset(flag,0,sizeof(flag));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(stap,0,sizeof(stap));
    for(int i=1;i<=n;i++) scc[i]=i,minscc[i]=mod;
}
void tarjan(int u){   flag[u]=1;
    dfn[u]=low[u]=++step;
    stap[++num]=u;//压栈
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (dfn[v]==0)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (flag[v]==1)
            low[u]=min(low[u],dfn[v]);
    }
    int v;
    if (dfn[u]==low[u])
    { 
        Scc++;//联通块标号
        int cnt=0;
        vector<int>tmp;
        do{
            v=stap[num--];
            flag[v]=0;
            scc[v]=Scc;//v属于第Scc个联通块
            minscc[Scc]=min(minscc[Scc],w[v]);
            tmp.push_back(w[v]);
            if(u==v) continue;
        }
        while (v!=u);
        for(auto v:tmp){
            if(v==minscc[Scc]) p[Scc]++;
        }
    }
}
queue<int>q;
void out( )
{    
   long long ans=0;
   for(int i=1;i<=Scc;i++) ans=(ans+minscc[i]);
   long long way=1;
   for(int i=1;i<=Scc;i++) way=way*p[i]%mod;
   cout<<ans<<" "<<way%mod;
}
int main( )
{
    //freopen("lys.in","r",stdin);
    cin>>n;
    init();
    for(int i=1;i<=n;i++) cin>>w[i];
    cin>>m;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        add(a,b);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    
     out();
}