题目链接

评测记录

评测记录（开O2 70分）

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<stack>
#define N 100005
using namespace std;
int n,m,idx,scc;
int dfn[N],low[N],ins[N],bel[N],cost[N],scc_cost[N],scc_node[N]; // ins：是否在栈里 bel：节点属于第几个强连通分量 cost：节点花费 scc_cost：强连通分量中的节点的最小花费 scc_node：强连通分量中节点花费等于最小花费的节点数量 
const int MOD=1e9+7;
stack<int> S;
vector<int> V[N];
void tarjan(int u) {
	int v;
	dfn[u]=low[u]=++idx;
	S.push(u);
	ins[u]=1;
	for(int i=0 ; i<V[u].size() ; i++) {
		v=V[u][i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		scc++;
		scc_cost[scc]=1e9+1;
		do {
			v=S.top();
			S.pop();
			ins[v]=0;
			bel[v]=scc;
		} while(u!=v);
	}
}
int main() {
	cin>>n;
	for(int i=1 ; i<=n ; i++) cin>>cost[i];
	cin>>m;
	for(int i=1 ; i<=m ; i++) {
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
	} //输入
	for(int i=1 ; i<=n ; i++)
		if(!dfn[i]) tarjan(i); //tarjan
	for(int i=1 ; i<=scc ; i++)
		for(int j=1 ; j<=n ; j++)
			if(bel[j]==i) scc_cost[i]=min(scc_cost[i],cost[j]); //更新强连通分量的cost
	for(int i=1 ; i<=scc ; i++)
		for(int j=1 ; j<=n ; j++)
			if(bel[j]==i && cost[j]==scc_cost[i]) scc_node[i]++; //计算强连通分量的min方案
	for(int i=1 ; i<=scc ; i++) 
		if(scc_node[i]==0) scc_node[i]=1; //乘法原理， 赋值为1 
	int ans1=0,ans2=1;
	for(int i=1 ; i<=scc ; i++) {
		ans1+=scc_cost[i];
		ans2=(ans2*scc_node[i])%MOD;
	}
	cout<<ans1<<' '<<ans2;
	return 0;
}

多谢大佬/bx/bx