Loading...

洛谷P3388 缩点

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

首先,缩点的前提是用$tarjan$求出强连通分量,这里就不讲了因为我讲不清楚

找出所有强连通分量之后,我们只需要将强连通分量根据以前的连接来进行重新建图即可

最后跑一边$O(n)$的$toposort$其实跑$n$遍$spfa$好像也能过

上代码qwq

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int next,to;
}e[200010];
stack<int> st;
int dfn[10010],low[10010];
int belong[10010],num[10010],num_point[10010];
int nows[10010];
int n,m,head[10010];
int ind[10010];
int tindex,na;
int x[100010],y[100010];
void add(int x,int y)
{
    tindex++;
    e[tindex].to=y;
    e[tindex].next=head[x];
    head[x]=tindex;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++tindex;
    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(dfn[u]==low[u])
    {
        na++;
        while(1)
        {
            int qwq=st.top();
            st.pop();
            num[na]+=num_point[qwq];
            nows[na]+=num_point[qwq];
            belong[qwq]=na;
            if(qwq==u)
            {
                break;
            }    
        }
    }
}
void dotarjan()
{
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
}
void doreduce()
{
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    for(int i=1;i<=m;i++)
    {
        if(belong[x[i]]!=belong[y[i]])
        {
            add(belong[x[i]],belong[y[i]]);
            ind[belong[y[i]]]++;
        }
    }
} 
void toposort()
{
    queue<int> q;
    for(int i=1;i<=na;i++)
    {
        if(ind[i]==0)
        {
            q.push(i);
        }
    } 
    int ans=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            num[v]=max(num[v],nows[v]+num[u]);
            ind[v]--;
            if(!ind[v])
            {
                q.push(v);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num_point[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        add(x[i],y[i]);
    }
    tindex=0;
    dotarjan();
    doreduce();
    toposort();
    int ans=0;
    for(int i=1;i<=na;i++)
    {
        ans=max(ans,num[i]);
    }
    cout<<ans;
}

chevron_left $dp$训练集合
数位$dp$小结 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名