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

草鉴定Grass Cownoisseur

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

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

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

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

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

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

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

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

SPFA求最长路即可

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

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

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

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<queue>
 4 #define N 100010
 5 #define min(a,b) (a<b?a:b)
 6 int n,m,head[N],to[N],next[N],num;
 7 const int ch_top=4e7+3;
 8 char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
 9 inline int read(){
10     while(*++now_r<'0');
11     register int x=*now_r-'0';
12     while(*++now_r>='0')x=x*10+*now_r-'0';
13     return x;
14 }
15 struct HA{
16     int pos,val;
17 };
18 struct cmp{
19     inline bool operator()(HA a,HA b){
20         return a.val>b.val;
21     }
22 };
23 std::priority_queue< HA, std::vector<HA>, cmp > q;
24 int dfn[N],low[N],tot;
25 int size[N<<1],belong[N],cnt;
26 int stack[N],top;
27 bool ins[N];
28 void Tarjan(int u){
29     dfn[u]=low[u]=++tot;
30     stack[++top]=u; ins[u]=1;
31     for(int i=head[u];i;i=next[i]){
32         int v=to[i];
33         if(!dfn[v]){
34             Tarjan(v);
35             low[u]=min(low[u],low[v]);
36         }
37         else if(ins[v])
38             low[u]=min(low[u],dfn[v]);
39     }
40     if(dfn[u]==low[u]){
41         belong[u]=++cnt;
42         size[cnt]=1;
43         while(stack[top]!=u){
44             int k=stack[top];
45             belong[k]=cnt;
46             ++size[cnt];
47             ins[k]=0; --top;
48         } --top; ins[u]=0;
49     }
50 }
51 int Head[N<<2],Next[N<<2],To[N<<2],Num,dis[N<<1];
52 bool inque[N<<2];
53 int main()
54 {
55     fread(ch,1,ch_top,stdin);
56     n=read(); m=read();
57     int x,y;
58     for(int i=1;i<=m;i++){
59         x=read(); y=read();
60         to[++num]=y;
61         next[num]=head[x];
62         head[x]=num;
63     }
64     for(int i=1;i<=n;i++)
65         if(!dfn[i]) Tarjan(i);
66     for(int i=1;i<=cnt;i++) size[i+cnt]=size[i];
67     for(int i=1;i<=n;i++)
68       for(int j=head[i];j;j=next[j]){
69         int v=to[j]; x=belong[i],y=belong[v];
70         if(x==y) continue;
71         To[++Num]=y; Next[Num]=Head[x];
72         Head[x]=Num; To[++Num]=x+cnt;
73         Next[Num]=Head[y]; Head[y]=Num;
74         To[++Num]=y+cnt;
75         Next[Num]=Head[x+cnt];
76         Head[x+cnt]=Num;
77       }
78     std::fill(dis,dis+1+cnt*2,-10000000);
79     dis[belong[1]]=0;
80     q.push((HA){belong[1],0});
81     while(!q.empty()){
82         int u=q.top().pos; inque[u]=0;
83         q.pop();
84         for(int i=Head[u];i;i=Next[i]){
85             int v=To[i];
86             if(dis[v]>dis[u]+size[v]) continue;
87             dis[v]=dis[u]+size[v];
88             if(!inque[v]){
89                 inque[v]=1;
90                 q.push((HA){v,dis[v]});
91             }
92         }
93     }
94     printf("%d
",dis[belong[1]+cnt]);
95     return 0;
96 }