P4129 [SHOI2006]仙人掌

· · 题解

前言

这里是题目。

主体代码没问题，高精度愣是搞了好久。。。

思路

这题我们首先要判断图是不是仙人掌，然后要求出把仙人掌进行删边之后得到的图仍然是连通图的方案数。

先看看这个方案数怎么求。

对于一个仙人掌图进行删边操作，显然我们只能删环上的边。对于每一个环，我们可以选择任意一条边删掉，也可以选择不删。设第 i 个环的边数为 num_i，我们可以这样计算得到答案 ans：

ans = \prod\limits_{i=1}^{\texttt{环的总数}}num_i + 1

然后问题就变成了怎么求环和 num_i。

我们可以用 \text{dfs}，构造出图的生成树。在 \text{dfs} 的过程中，我们可以记录下每个节点 x 的初始访问时间 dfn_x 和能够往上最大程度追溯到的节点 low_x。如果走了返租边（访问到了访问过的节点），那么说明出现了环。

那环的边数呢？我们构造出来生成树，如果有返租边，那么一定是先一直向下访问、构造，然后到了某个节点 a 就突然往上到了另一个节点 b。由于我们一直向下构造，再加上一条边回到 b，出现了一个环，所以这个环的边数就是我们从 b 一直向下走到 a 走的边数加上这条返租边。这个边数我们可以用深度的差得到，设第 i 个节点的深度为 dep_i，则环的边数为 dep_b - dep_a + 1。

剩下的问题是怎么判断图是不是仙人掌了。由图观察可知，如果 某个节点的子孙的返租边到了这个节点之上 与 这个节点发出的返租边 的和 \ge 2，那么就说明这个节点在两个环里了，该图不是仙人掌。

您可能要问为啥不用 \text{bfs}，因为这个菜鸡认为 \text{bfs} 有点难搞，并且比较擅长 \text{dfs}。 \text{dfs} 可以构造出生成树，比较好处理点或边出现的顺序关系（例如可以处理深度，利用 dfn 和 low 处理环），所以选择用 \text{dfs}。

代码

注意最后的答案可能是一个很大很大的数。

我们要用高精度存答案。

可能要用压位高精，因为这个菜鸡 MLE 了好多发，最后把 base 改成 1e14 才过的。

void dfs(int x, int fa) {
    ++num;
    int cnt = 0;                         // 求该节点所在环的个数 
    dfn[x] = low[x] = ++tot;
    for (int i = he[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fa) continue; 
        if (!dfn[y]) {                   // 如果是树枝边 
            dep[y] = dep[x] + 1;         // 计算深度 
            dfs(y, x);
            low[x] = min(low[x], low[y]);// 求最大程度追溯的节点 
            if (low[y] < dfn[x]) ++cnt;  // 有个儿子的返租边在 y 之上，注意这里是 < ，题目中说的是边 
        } else if (dfn[y] < dfn[x]) {    // 是返租边 
            if (dep[x] - dep[y] > 1) ans = ans * (dep[x] - dep[y] + 2); // 计算答案 
            ++cnt;
            low[x] = min(low[x], dfn[y]);// 求最大程度追溯的节点 
        }
        if (cnt == 2) ok = 0;            // 不是仙人掌 
    }
}
int main() {
    ans = 1;
    n = read(), m = read();
    for (int i = 1, t, lst; i <= m; ++i) {
        t = read(), lst = read();
        for (int j = 2, x; j <= t; ++j) {
            x = read();
            e[++tot] = x, ne[tot] = he[lst], he[lst] = tot;
            e[++tot] = lst, ne[tot] = he[x], he[x] = tot;
            lst = x;
        }
    }
    tot = 0;
    dfs(1, 1);
    if (num != n) ok = 0;               // 不连通    
    if (ok) ans.pr();
    else puts("0");
    return 0;
}

后记

建议先写主体部分再加高精板子，要不然很难知道是哪里出了问题。用 int 能有 70 分。