自动搬运

查看原文

来自洛谷，原作者为

	扬皓2006 我们的相遇，就是千万分之一的奇迹。

搬运于2025-08-24 21:35:01，当前版本为作者最后更新于2019-10-15 12:36:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实我本人是反对烧情侣的

因为我喜欢一个特勇的女孩纸,但是总是泡不到（OIer共性）

好了，进入正题

此题为Tarjan

我就说一下方案数怎么算

就是乘法原理：各个强连通分量中最小花费点的个数相乘

上代码:

#include<bits/stdc++.h>//万能头
#define maxn 100001
#define maxm 300005
using namespace std;
struct Edge{
	int nex,to;
}edge[maxm];
int low[maxn],dfn[maxn],k[maxm],c[maxm],du[maxm],hea[maxm],stac[maxn],ins[maxn],a[maxn];
int top,tot,n,m,num,cnt;
long long ans1,ans2=1,mo=1e9+7;//ans1,ans2一定要longlong不然可能会炸
vector<int>scc[maxm];
void add(int x,int y)
{
	edge[++tot].nex=hea[x];
	edge[tot].to=y;
	hea[x]=tot; 
}//存下一条<x.y>的弧
void tarjan(int x)//Tarjan1经典模板
{
	dfn[x]=low[x]=++num;
	stac[++top]=x;ins[x]=1;
	for(int i=hea[x];i;i=edge[i].nex)
	{
		int y=edge[i].to;
		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])
	{
		int z;cnt++;
		do{
			z=stac[top--];ins[z]=0;c[z]=cnt;k[cnt]++;scc[cnt].push_back(z);
		}while(x!=z);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);//存边
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])  tarjan(i);//如果未被搜索就Tarjan
	}
	for(int i=1;i<=cnt;i++)
	{
		int coun=1,x=0x3fffffff;
		int len=scc[i].size();
		for(int j=0;j<len;j++)
		{
			if(a[scc[i][j]]==x) coun++;//如果一样就++
		    if(a[scc[i][j]]<x)
		    {
			    x=a[scc[i][j]];
			    coun=1;
		    }//如果小于就重置
		}
		ans1+=x;
		ans2*=coun;
		ans2%=mo;
	}
	cout<<ans1<<" "<<ans2;
	return 0;
}

最后，祝各位OIer都能A过此题（不抄题解），也祝你们能够追到自己心仪的妹子！

管理大大给个通过呗