题解 P2921 【[USACO08DEC]在农场万圣节Trick or Treat on the Farm】

做完以后粗略翻了下题解，发现都是 $Tarjan$ 或记忆化搜索，总之逃不出 $dfs$，所以我就把我的非递归方法贡献一下吧。 事实上，这道题用 $Tarjan$ 是大材小用了。此题不需要任何算法，两层简单的循环就能解决。 首先我们需要注意到一点，虽然此题也是一张有向图，但是每个点的出度有且只有 “1”。这说明什么？不需要递归，直接沿着这条唯一的路径走下去就行了...... ### 一、为了实现这一方法，我们对每个点设置两个属性： 1、颜色 $(color)$ ： 此节点第一次被访问时，这条访问他的路径是由那个节点发出的（起点）。 2、时间戳 $(dfn)$ ：此节点第一次被访问时，他到发出这条路径的起点的距离（发出节点的 $dfn = 0$，第二个被访问的节点的 $dfn = 1$，第三个 $dfn = 2$ ......） 有了这两个属性，我们就可以计算环的大小，方法如下： 1、从某一节点发出路径 2、走到某个节点上（包括起点），如果这个节点没有被染色，那么染成自己的颜色，并标记上 $dfn$ 3、走到某个节点上，如果这个节点已经被染成了自己的颜色，那么环的大小就出来了：当前时间 $(cnt)$ $-$ 此节点 $dfn$ 到了这一步，实际上已经解决了另一个更简单的问题：[NOIP2015 信息传递](https://www.luogu.org/problemnew/show/P2661)。 接下来就是本题特色了 ### 二、对于每一只奶牛（或者说每一个起点、颜色、路径），我们记录如下两个属性： 1、环的大小 $(minc)$ ：每条路径最终都会进入环中，或者起点本身就在环中，我们记录下这个环的大小为之后服务 2、入环时间戳 $(sucdfn)$ ：这条路径什么时候会进入环中，同样是为之后服务的一个属性 首先讲解一下如果得到这两个属性： 1、在上一节中我们已经讲了如何初步获取环的大小，入环时间戳只要记录为那个交点的时间戳即可 2、如果走到了之前走过的节点，那么新的路径必然进入之前路径的环中，直接把这个环的大小要过来就行了。入环时间戳则分两种情况： i. 如果这个节点不在环中，“原路径的入环时间戳 $-$ 原路径中此节点的时间戳 +　新路径当前时间”　即为新路径的入环时间戳; ii. 而如果这个节点在环中，直接就是新路径当前时间。 iii. 判断方法则是 “原路径的入环时间戳 $-$ 原路径中此节点的时间戳” 是否大于 $0$，综合起来就是：“$max($原路径的入环时间戳 $-$ 原路径中此节点的时间戳$, \;0)$ +　新路径当前时间” ### 三、把上面的问题都解决了，出答案就太简单了： 1、第一节中的发现环的大小之后，答案就是“当前时间” 2、第二节中与之间走过的节点相遇并记录完信息后，答案是 “入环时间戳 + 环的大小” 至此本题已经完美解决，且没有用到任何算法。贴代码： ```cpp #include<bits/stdc++.h> using namespace std; const int maxn = 100000 + 5; int n; int nxt[maxn]; int color[maxn]; int sucdfn[maxn]; int dfn[maxn]; int minc[maxn]; void Init() { cin >> n; for(int i = 1; i <= n; ++i) cin >> nxt[i]; memset(color, 0, sizeof(color)); memset(dfn, 0, sizeof(dfn)); memset(minc, 0, sizeof(minc)); } void Solve() { for(int cow = 1; cow <= n; ++cow) { for(int i = cow, cnt = 0; ; i = nxt[i], ++cnt) { if(!color[i]) { color[i] = cow; dfn[i] = cnt; } else if(color[i] == cow) { minc[cow] = cnt - dfn[i]; sucdfn[cow] = dfn[i]; cout << cnt << endl; break; } else { minc[cow] = minc[color[i]]; sucdfn[cow] = cnt + max(sucdfn[color[i]] - dfn[i], 0); cout << sucdfn[cow] + minc[cow] << endl; break; } } } } int main() { Init(); Solve(); return 0; } ```