洛谷 P3119 [USACO15JAN]草鉴定Grass Cownoisseur 题解【tarjan】【SPFA】

点击量：209

目录

Description

In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields. For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X.

Bessie the cow, as we all know, enjoys eating grass from as many fields as possible. She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once).

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ’s paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route. She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Please compute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction. Bessie can only travel backwards at most once in her journey. In particular, she cannot even take the same path backwards twice.

Input

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000).

The following M lines each describe a one-way cow path. Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y. The same cow path will never appear more than once.

Output

A single line indicating the maximum number of distinct fields Bessie

can visit along a route starting and ending at field 1, given that she can

follow at most one path along this route in the wrong direction.

Sample

Input:

7 10 
1 2 
3 1 
2 5 
2 4 
3 7 
3 5 
3 6 
6 5 
7 2 
4 7 

Output:

6 

Note

Here is an ASCII drawing of the sample input:

v---3-->6
7   | \ |
^\  v  \|
| \ 1   |
|   |   v
|   v   5
4<--2---^

Bessie can visit pastures 1, 2, 4, 7, 2, 5, 3, 1 by traveling backwards on the path between 5 and 3. When she arrives at 3 she cannot reach 6 without following another backwards path.

题意

给定一张$ n(\le 100,000)$个节点，$ m(\le 100,000)$条边的有向图。从1号点出发回到1号点，其中可以逆行一次。问最多能经过多少个不同的点。

题解

在有向图中，强连通分量中的点肯定随时可以互达，因此先缩点重建图，此时得到一个DAG。

可以逆行一次容易想到分层图，但是只逆行一次有点大材小用。而且一个点可能被算两遍，因此分层图是不可取的。

而且1号点所在的强连通分量的入度不一定为1，因此在拓扑排序上也可能碰壁。

既然只逆行一次，那么我们枚举逆行哪条边。在DAG中改变一条边的方向，就可能形成环，此时答案就是这个环（强连通分量）的大小。

当不逆行的时候，出了1号点所在的强连通分量，在DAG中就再也回不来了，因此答案最少是1号点所在强连通分量的大小。

接下来是计算环。假设我们枚举到了边$ u\to v$，令$ dis_1[i]$表示$ 1\to i$的最长路；$ dis_2[i]$表示$ i\to 1$的最长路。此时拿$ dis_1[v]+dis_2[u]$更新答案。

如果最长路包含了起点终点，那么需要额外减去1号点所在强连通分量所带来的贡献；如果只包含终点，那么还需要加上$ u$所在强连通分量的大小。

总而言之，求环的时候要做到不重不漏。

Code：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
struct edge
{
    int from,n,nxt;
    edge(int from,int n,int nxt)
    {
        this->from=from;
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
    friend bool operator <(edge a,edge b)
    {
        if(a.from!=b.from)
            return a.from<b.from;
        return a.n<b.n;
    }
    friend bool operator ==(edge a,edge b)
    {
        return a.from==b.from&&a.n==b.n;
    }
}e[200100];
int head[100100],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(from,to,head[from]);
    head[from]=ecnt;
}
int dfn[100100],low[100100],dcnt=0,stk[100100],tp=0;
bool in[100100];
int del[100100],cnt=0,sz[100100];
void tarjan(int x)
{
    dfn[x]=++dcnt;
    low[x]=dfn[x];
    stk[++tp]=x;
    in[x]=1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(!dfn[e[i].n])
        {
            tarjan(e[i].n);
            low[x]=low[x]<low[e[i].n]?low[x]:low[e[i].n];
        }
        else if(in[e[i].n])
            low[x]=low[x]<dfn[e[i].n]?low[x]:dfn[e[i].n];
    if(dfn[x]==low[x])
    {
        ++cnt;
        do
        {
            del[stk[tp]]=cnt;
            in[stk[tp--]]=0;
            ++sz[cnt];
        }while(stk[tp+1]!=x);
    }
}
int dis[100100],f[100100];
bool used[100100];
void spfa(int x)
{
    using std::queue;
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    dis[x]=-sz[x];
    q.push(x);
    used[x]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        used[x]=0;
        for(int i=head[x];~i;i=e[i].nxt)
            if(dis[e[i].n]>dis[x]-sz[e[i].n])
            {
                dis[e[i].n]=dis[x]-sz[e[i].n];
                if(!used[e[i].n])
                    q.push(e[i].n);
                used[e[i].n]=1;
            }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i);
    for(int i=0;i<=ecnt;++i)
    {
        e[i].from=del[e[i].from];
        e[i].n=del[e[i].n];
    }
    std::sort(e,e+ecnt+1);
    std::unique(e,e+ecnt+1);
    for(int i=0;i<ecnt;++i)
        if((e[i]<e[i+1])==false)
        {
            ecnt=i;
            break;
        }
    memset(head,-1,sizeof(head));
    int tt=ecnt;
    for(int i=0;i<=tt;++i)
        if(e[i].from!=e[i].n)
            add(e[i].from,e[i].n);
    spfa(del[1]);
    for(int i=1;i<=cnt;++i)
        f[i]=dis[i];
    memset(head,-1,sizeof(head));
    ecnt=tt;
    for(int i=0;i<=tt;++i)
        if(e[i].from!=e[i].n)
            add(e[i].n,e[i].from);
    spfa(del[1]);
    int ans=sz[del[1]];
    for(int i=0;i<=tt;++i)
        if(e[i].n!=e[i].from)
            ans=std::max(ans,-f[e[i].n]-dis[e[i].from]-sz[del[1]]);
    printf("%d\n",ans);
    return 0;
}