草鉴定Grass Cownoisseur

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

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

如果没有逆行操作和回到1的限制，我们很容易想到一种方法：

Tarjan缩点，再记忆化搜索/拓扑排序一遍，求出一条最长的链

如果加上回到1的限制：只能走一遍1所在的连通块

再加上逆行操作，就有些复杂了，

因为只有一次逆行操作，我们可以建一个分层图，

第一层的点和第二层的点连一条与第一层中方向相反的边

SPFA求最长路即可

为什么不会走除了1以外重复的点：若到达第二层后，

又走到了在第一层中走过的点，由于DAG的性质，

它是无法再走到1的，不会产生影响

 #include<algorithm>

 #include<cstdio>

 #include<queue>

 #define N 100010

 #define min(a,b) (a<b?a:b)

 int n,m,head[N],to[N],next[N],num;

 const int ch_top=4e7+;

 char ch[ch_top],*now_r=ch-,*now_w=ch-;

 inline int read(){

     while(*++now_r<'');

     register int x=*now_r-'';

     while(*++now_r>='')x=x*+*now_r-'';

     return x;

 }

 struct HA{

     int pos,val;

 };

 struct cmp{

     inline bool operator()(HA a,HA b){

         return a.val>b.val;

     }

 };

 std::priority_queue< HA, std::vector<HA>, cmp > q;

 int dfn[N],low[N],tot;

 int size[N<<],belong[N],cnt;

 int stack[N],top;

 bool ins[N];

 void Tarjan(int u){

     dfn[u]=low[u]=++tot;

     stack[++top]=u; ins[u]=;

     for(int i=head[u];i;i=next[i]){

         int v=to[i];

         if(!dfn[v]){

             Tarjan(v);

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

         }

         else if(ins[v])

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

     }

     if(dfn[u]==low[u]){

         belong[u]=++cnt;

         size[cnt]=;

         while(stack[top]!=u){

             int k=stack[top];

             belong[k]=cnt;

             ++size[cnt];

             ins[k]=; --top;

         } --top; ins[u]=;

     }

 }

 int Head[N<<],Next[N<<],To[N<<],Num,dis[N<<];

 bool inque[N<<];

 int main()

 {

     fread(ch,,ch_top,stdin);

     n=read(); m=read();

     int x,y;

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

         x=read(); y=read();

         to[++num]=y;

         next[num]=head[x];

         head[x]=num;

     }

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

         if(!dfn[i]) Tarjan(i);

     for(int i=;i<=cnt;i++) size[i+cnt]=size[i];

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

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

         int v=to[j]; x=belong[i],y=belong[v];

         if(x==y) continue;

         To[++Num]=y; Next[Num]=Head[x];

         Head[x]=Num; To[++Num]=x+cnt;

         Next[Num]=Head[y]; Head[y]=Num;

         To[++Num]=y+cnt;

         Next[Num]=Head[x+cnt];

         Head[x+cnt]=Num;

       }

     std::fill(dis,dis++cnt*,-);

     dis[belong[]]=;

     q.push((HA){belong[],});

     while(!q.empty()){

         int u=q.top().pos; inque[u]=;

         q.pop();

         for(int i=Head[u];i;i=Next[i]){

             int v=To[i];

             if(dis[v]>dis[u]+size[v]) continue;

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

             if(!inque[v]){

                 inque[v]=;

                 q.push((HA){v,dis[v]});

             }

         }

     }

     printf("%d\n",dis[belong[]+cnt]);

     return ;

 }

草鉴定Gras

【洛谷P3119】[USACO15JAN]草鉴定Grass Cownoisseur

草鉴定Grass Cownoisseur