题解 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 信息传递。 接下来就是本题特色了

二、对于每一只奶牛(或者说每一个起点、颜色、路径),我们记录如下两个属性:

1、环的大小 $(minc)$ :每条路径最终都会进入环中,或者起点本身就在环中,我们记录下这个环的大小为之后服务

2、入环时间戳 $(sucdfn)$ :这条路径什么时候会进入环中,同样是为之后服务的一个属性

首先讲解一下如果得到这两个属性:

1、在上一节中我们已经讲了如何初步获取环的大小,入环时间戳只要记录为那个交点的时间戳即可

2、如果走到了之前走过的节点,那么新的路径必然进入之前路径的环中,直接把这个环的大小要过来就行了。入环时间戳则分两种情况:

i. 如果这个节点不在环中,“原路径的入环时间戳 $-$ 原路径中此节点的时间戳 + 新路径当前时间” 即为新路径的入环时间戳;

ii. 而如果这个节点在环中,直接就是新路径当前时间。

iii. 判断方法则是 “原路径的入环时间戳 $-$ 原路径中此节点的时间戳” 是否大于 $0$ ,综合起来就是:“ $max($ 原路径的入环时间戳 $-$ 原路径中此节点的时间戳 $, \;0)$ + 新路径当前时间”

三、把上面的问题都解决了,出答案就太简单了:

1、第一节中的发现环的大小之后,答案就是“当前时间”

2、第二节中与之间走过的节点相遇并记录完信息后,答案是 “入环时间戳 + 环的大小”

至此本题已经完美解决,且没有用到任何算法。贴代码:

#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;
}

发表于 2018-06-24 15:52:10 in 题解