Loading...

洛谷P2193 HXY烧情侣

check评论:0 条 remove_red_eye浏览量:393 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-14

裸的$tarjan$ $\text{qwq}$

我们求出所有强连通分量后,把每个里面的最小值加起来就好$\text{qwq}$

#include <bits/stdc++.h>
using namespace std;
int dfn[100010],low[100010],na,minn[100010],cnt;
int belong[100010],a[100010],n,m,head[100010];
struct edge
{
    int next,to;
}e[600010];
vector<int> point[100010];
stack<int> st;
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    st.push(u);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!belong[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u])
    {
        na++;
        while(1)
        {
            int v=st.top();
            st.pop();
            belong[v]=na;
            point[na].push_back(v);
            minn[na]=min(minn[na],a[v]);
            if(v==u)
            {
                break;
            }
        }
    }
}
void dotarjan()
{
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
}
int main()
{
    memset(minn,0x3f,sizeof(minn));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    cnt=0;
    dotarjan();
    int ans1=0,ans2=1;
    for(int i=1;i<=na;i++)
    {
        ans1+=minn[i];
        int k=0;
        for(int j=0;j<point[i].size();j++)
        {
            if(a[point[i][j]]==minn[i])
            {
                k++;
            }
        }
        ans2*=k;
    }
    cout<<ans1<<" "<<ans2;
}


暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名