P3119 [USACO15JAN]草鉴定Grass Cownoisseur

题目描述

约翰有\(n\)块草场，编号1到\(n\)，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。

贝西总是从1号草场出发，最后回到1号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。

输入输出格式

输入格式：

第一行：草场数\(n\)，道路数\(m\)。

以下\(m\)行，每行\(x\)和\(y\)表明有\(x\)到\(y\)的单向边，不会有重复的道路出现。

输出格式：

一个数，逆行一次最多可以走几个草场。

数据范围：

\(1<=N,M<=100,000\)

思路：先缩点，以新点的大小为点权，正反跑最长路，枚举每条边上的两个点更新答案。

需要注意的是，\(dis\)数组得先置\(-inf\)，因为\(dis==0\)表示不可以到，但它可能更新答案。就这个卡了我两个月直到今天一位洛谷群群友@ysj1173886760才告诉我原因真是万分感谢

Code:

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int N=100010;

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

struct Edge

{

    int to,next;

}edge[N];

struct Edge0

{

    int to,next,w;

}edge0[N<<1];

int head[N],cnt=0,head0[N],cnt0=0;

void add(int u,int v)

{

    edge[++cnt].next=head[u];edge[cnt].to=v;head[u]=cnt;

}

void add0(int u,int v,int w)

{

    edge0[++cnt0].next=head0[u];edge0[cnt0].to=v;edge0[cnt0].w=w;;head0[u]=cnt0;

}

int n,m;

int time=0,tot,s[N],dfn[N],is[N],low[N],ha[N],n0=0,siz[N],m_max=0,typ[N];

void tarjan(int now)

{

    dfn[now]=low[now]=++time;

    is[now]=1;

    s[++tot]=now;

    for(int i=head[now];i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(!dfn[v])

        {

            tarjan(v);

            low[now]=min(low[now],low[v]);

        }

        else if(is[v])

            low[now]=min(low[now],dfn[v]);

    }

    if(dfn[now]==low[now])

    {

        int k;n0++;

        do

        {

            k=s[tot--];

            siz[n0]++;

            is[k]=0;

            ha[k]=n0;

        }while(k!=now);

    }

}

queue <int > q;

int used[N],dis[N];

void spfa(int ty)

{

    q.push(ha[1]);

    memset(used,0,sizeof(used));

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        used[u]=0;

        for(int i=head0[u];i;i=edge0[i].next)

        {

            int v=edge0[i].to,w=edge0[i].w;

            if(w!=ty) continue;

            if(dis[v]<dis[u]+siz[v])

            {

                dis[v]=dis[u]+siz[v];

                if(!used[v])

                {

                    used[v]=1;

                    typ[v]=ty;

                    q.push(v);

                }

            }

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        add(u,v);

    }

    for(int i=1;i<=n;i++)

        if(!dfn[i])

            tarjan(i);

    for(int i=1;i<=n;i++)

        for(int j=head[i];j;j=edge[j].next)

        {

            int v=edge[j].to;

            if(ha[i]!=ha[v])

            {

                add0(ha[i],ha[v],1);

                add0(ha[v],ha[i],0);

            }

        }

    memset(dis,-0x3f,sizeof(dis));

    dis[ha[1]]=0;

    spfa(1);

    spfa(0);

    for(int i=1;i<=n0;i++)

        if(ha[1]!=i)

            for(int j=head0[i];j;j=edge0[j].next)

            {

                int v=edge0[j].to,w=edge0[j].w;

                if((typ[i]^typ[v]||ha[1]==v)&&typ[i]^w)

                    m_max=max(m_max,dis[i]+dis[v]);

            }

    printf("%d\n",m_max+siz[ha[1]]);

    return 0;

}

2018.7.26

巴特西

洛谷 P3119 [USACO15JAN]草鉴定Grass Cownoisseur 解题报告