zcmimi's blog
查看原题

点击跳转

可以说是很水吧

缩点后每个环只需要环上最小的费用就可以保证环安全

一个环方案数为环上最小值的数量

总方案数为所有环方案数的乘积

(一个点也算一个环)

#include<bits/stdc++.h>
const int N=100011,P=1000000007;
int n,m,cnt,a[N],head[N];
struct edge{int to,nxt;}e[N*3];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
int dfn[N],low[N],sz,st[N],tp,c[N],t[N];bool v[N];
void cmin(int&x,int y){if(y<x)x=y;}
long long ans=0,ANS=1;
void tarjan(int x){
    dfn[x]=low[x]=++sz;v[x]=1;st[++tp]=x;
    fl(i,x)if(!dfn[to]){
        tarjan(to);
        cmin(low[x],low[to]);
    }else if(v[to])
        cmin(low[x],dfn[to]);
    if(low[x]==dfn[x]){
        int c=a[x],t=1,k;
        while(k=st[tp--]){
            v[k]=0;if(k==x)break;
            if(a[k]<c)c=a[k],t=1;
            else if(a[k]==c)++t;
        }
        ans+=c;ANS=ANS*t%P;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    scanf("%d",&m);
    int x,y;
    for(int i=1;i<=m;++i)
        scanf("%d%d",&x,&y),add(x,y);
    for(int i=1;i<=n;++i)
        if(!dfn[i])tarjan(i);
    printf("%lld %lld\n",ans,ANS);
}
LG CF427C Checkposts
comment评论
Search
search