题解 P3119 【[USACO15JAN]草鉴定Grass Cownoisseur】

· · 题解

博客观看效果更佳

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

显然先tarjan缩点，染色后建一张新图

对于一次逆行机会的处理，我们就再建一张一模一样的图（第二层）

对于每条给定的有向边(u,v)，建一条从第一层向第二层的反边(v,u+n)

有一个细节需要注意，建了分层图之后，一定要把第一层的缩点的大小赋给第二层

然后再在分层图上跑从color[1]节点到其它点的最长路

对于输出的答案，需要注意是max(dis[color[1]],dis[color[1+n]])

因为有可能不反悔就是最优解了

对于分层图，空间一定要开够（至少是普通图的层数倍）

顺便推荐一道分层图好题：[JLOI2011]飞行路线

代码：

#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 
*/