【LGOI3319】草鉴定

一个有向图，有一次逆行机会
从一号点开始回到一号点
最多可以通过多少个点

现在打tarjan打得得心应手，一下子就敲完了

显然先tarjan缩点，染色后建一张新图
对于一次逆行机会的处理，我们就再建一张一模一样的图（第二层）
对于每条给定的有向边\((u,v)\)，建一条从第一层向第二层的反边\((v,u+n)\)

有一个细节需要注意，建了分层图之后，一定要把第一层的缩点的大小赋给第二层
然后再在分层图上跑从\(color[1]\)节点到其它点的最长路

对于输出的答案，需要注意是\(max(dis[color[1]],dis[color[1+n]])\)
因为有可能不反悔就是最优解了

代码：

#include<bits/stdc++.h>
#define N 200005
using namespace std;

int n,m,u[N],v[N];

struct Edge
{
    int next,to;
}edge[N<<1];
int cnt=0,head[N];

inline void add_edge(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

int tms=0,low[N],dfn[N];
int co[N],sum[N],col=0;
stack<int> sta;
void tarjan(int u)
{
    low[u]=dfn[u]=++tms;
    sta.push(u);
    for(register int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!co[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        co[u]=++col;
        sum[col]++;
        while(sta.top()!=u)
        {
            co[sta.top()]=col;
            sum[col]++;
            sta.pop();
        }
        sta.pop();
    }
}

int bc;
int dis[N],vis[N];
queue<int> q;
void spfa()
{
    memset(dis,-100,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(bc); dis[bc]=0; vis[bc]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(register int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]<dis[u]+sum[u])
            {
                dis[v]=dis[u]+sum[u];
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}

int main()
{
    read(n);read(m);
    for(register int i=1;i<=m;++i)
    {
        read(u[i]);read(v[i]);
        add_edge(u[i],v[i]);
    }
    for(register int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    bc=co[1];
    cnt=0;
    memset(head,0,sizeof(head));
    for(register int i=1;i<=m;++i)
    {
        if(co[u[i]]==co[v[i]]) continue;
        add_edge(co[u[i]],co[v[i]]);//建缩点边
        add_edge(co[u[i]]+n,co[v[i]]+n);//建下一层
        add_edge(co[v[i]],co[u[i]]+n);//反边
    }
    for(int i=1;i<=col;++i) sum[i+n]=sum[i];
    spfa();
    printf("%d\n",max(dis[bc+n],dis[bc]));
    return 0;
}
/*
7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7
*/