P2194 HXY烧情侣 题解

· · 题解

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

因为我喜欢一个特勇的女孩纸,但是总是泡不到（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过此题（不抄题解），也祝你们能够追到自己心仪的妹子！

管理大大给个通过呗