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

· · 题解

本蒟蒻的Blog(戳这儿呀QwQ)

题解

单向道路？求一次能遍历到的最大点的数量？二话不说先上个Tarjan缩个点压压惊poi。

如果没有逆行这种操作，那么很显然起点所在强联通分量点的个数就是答案。

可是Bessie就是Bessie，总要搞点事情出来才符合她的性格。

于是乎我们缩点之后正反建图，刷两趟SPFA求每个点到起点的最长路。

然后枚举缩完点的图上的一条边，用来搞事情逆行。设当前枚举到的边为(u,v)，那么u在正建的图上到起点的最长路加上v在反建图上到起点的最长路就是逆行这条边时的最优解。在所有边里刷个最大值就行了呢poi。

有几个坑：

  1. 在最后计算答案时起点的权值会被算两次，记得减去一个。
  2. 枚举用于逆行的边时需要确保可以走到这条边并且走到这条边后可以走回起点。
  3. 由于需要建三套图(没缩过点的一套正建图一套反建图一套)，不要把数组名搞混了。此时封装可能是个好办法（但是会长一些，所以我没封装）。

其实总体上讲这题的想法并不难，但是代码有点难码QwQ。

于是乎这题就解完了。时间复杂度为\Theta(n)。

代码

我觉得我写的挺简洁的poi。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100005;
int n,m,tot[3],lnk[3][maxn],son[3][maxn],nxt[3][maxn],w[maxn],idx,dfn[maxn],low[maxn],top,stack[maxn],cnt,id[maxn],dist[3][maxn],que[maxn],ans;bool vis[maxn];
inline int read()
{
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
inline void add_e(int x,int y,int id){tot[id]++;son[id][tot[id]]=y;nxt[id][tot[id]]=lnk[id][x];lnk[id][x]=tot[id];}
void Tarjan(int now)   //Tarjan缩点大法好
{
    idx++;top++;vis[now]=true;
    dfn[now]=low[now]=idx;stack[top]=now;
    for(int i=lnk[0][now];i;i=nxt[0][i])
    {
        if(!dfn[son[0][i]])
        {
            Tarjan(son[0][i]);
            if(low[son[0][i]]<low[now]) low[now]=low[son[0][i]];
        }
        else if(vis[son[0][i]]&&dfn[son[0][i]]<low[now]) low[now]=dfn[son[0][i]];
    }
    if(dfn[now]==low[now])
    {
        cnt++;
        do
        {
            id[stack[top]]=cnt;w[cnt]++;
            vis[stack[top]]=false;top--;
        }while(stack[top+1]!=now);
    }
}
inline void SPFA(int id) //SPFA求最长路
{
    memset(vis,false,sizeof(vis));
    int hed=0,til=1;
    que[1]=::id[1];vis[que[1]]=true;dist[id][que[1]]=w[que[1]];
    while(hed!=til)
    {
        hed=(hed+1)%maxn;vis[que[hed]]=false;
        for(int j=lnk[id][que[hed]];j;j=nxt[id][j])
        {
            if(dist[id][que[hed]]+w[son[id][j]]>dist[id][son[id][j]])
            {
                dist[id][son[id][j]]=dist[id][que[hed]]+w[son[id][j]];
                if(!vis[son[id][j]])
                {
                    vis[son[id][j]]=true;
                    til=(til+1)%maxn;
                    que[til]=son[id][j];
                }
            }
        }
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)                  //建初始图
    {
        int a=read(),b=read();
        add_e(a,b,0);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);    //缩点
    for(int i=1;i<=n;i++)                //缩完点后正反建图
    {
        for(int j=lnk[0][i];j;j=nxt[0][j])
        {
            if(id[i]!=id[son[0][j]])
            {
                add_e(id[i],id[son[0][j]],1);
                add_e(id[son[0][j]],id[i],2);
            }
        }
    }
    SPFA(1);SPFA(2);
    for(int i=1;i<=cnt;i++)               //枚举逆行边，计算答案
        for(int j=lnk[2][i];j;j=nxt[2][j])
            if(dist[1][i]&&dist[2][son[2][j]]&&dist[1][i]+dist[2][son[2][j]]-w[id[1]]>ans)
                ans=dist[1][i]+dist[2][son[2][j]]-w[id[1]];
    printf("%d\n",ans);
    return 0;
}