题解：P3472 [POI 2008] MAF-Mafia

· · 题解

P3472 [POI 2008] MAF-Mafia link

合集：浅谈基环树

题目大意

有 n（1 \le n \le 10 ^ 6）个人，每个人都用枪指着一个人（可以是自己），给出每个人用枪指着的人，之后按照需按照一定顺序开枪，求可能的最小和最大的死亡人数。

解题思路

每个人与他指着的人建单向边，形成一个内向基环森林。

由于思路 1 并不能很好地解释，我们仍然采取思路 2 的观点，即把基环树看作挂着许多子树的环。

我们先分析最大值，考虑一个环，最少只有一个人活下来（特别地，自环的话是可以全部死亡，需要特判）。

我们再考虑一棵树，叶子节点一定不死，因为没有人指着他们，然后如果想要更多人死，那就要尽可能在一个人死之前就开枪，于是我们可以从根的儿子先开始开枪，然后一层一层地开枪，最后只有叶子会活下来。

那么，结合两种观点，如果这个环上有子树的话，先让环开枪，最后只让这个有子树的点活下来，最后让所有子树按照层数开枪，环上的那个点会死掉，其他不是叶子的也会死，也就是这棵子树只有叶子活下来。

所以，最大值可以分三种情况：

所有基环树存活数加起来，就能求得最小存活数，也就是最大死亡数。

我们再来分析最小值，根据上面的分析可以知道，叶子节点一定活下来。

递推可知，叶子节点的父亲必死，那么叶子节点的爷爷如果没有其他叶子指着就能活下来，然后一层层推广开来。

我们使用贪心思想，如果一个点是必死的，那我们绝对不让他在死前开枪，这一定是不优的，因为这个人的死亡最多能使其指向的点从死转到活，并不能使两个及以上的点由死到活以达到更优。

于是，我们可以发现活与死的等价条件：

基于这两个条件，我们可以采用递推的思想，一开始叶子的状态一定是确定的，然后让叶子去更新叶子父亲，叶子父亲去更新叶子爷爷，以此类推。

实现我们可以采取类似于拓扑排序的操作，先将度为 0 的点也就是叶子入队，然后每次次取出队首，更新其指向点的信息：

如此以来，最后还可能有一些状态没有确定的点，这些点只有可能是其中任何一个点都没有被标记必死的环（如果一个环有点被其儿子标上必死，那么这个环就被打开了一个缺口，最后整个基环树的状态都能被确定）。

所以，我们再便利所有点，如果这个点状态没有确定，就一直往其指着的点走，遍历这个环，并且都标记其状态，最后找出次环的长度，对于一个环，其最大存活数显然为 \frac{len}{2}，加上即可。

代码实现上，最小值可以和最大值一起处理，只需在进行拓扑排序时记录一个 vis 表示此环有没有环外的子树，最后在遍历环时将所有 vis 取或，为 0 就说明此环没有子树，需要将最大死亡数减 1。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e6 + 10;

int n, cnt;
int p[N], deg[N], st[N];
int ans1, ans2;
bool vis[N];
queue<int> q;

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    ans1 = ans2 = n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        deg[p[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!deg[i])
        {
            ans1--, ans2--;
            st[i] = 1;
            vis[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[p[x]] = 1;
        if (st[x] == 1)
        {
            if (st[p[x]] == 2)
            {
                continue;
            }
            st[p[x]] = 2;
            q.push(p[x]);
        }
        else
        {
            if (--deg[p[x]])
            {
                continue;
            }
            st[p[x]] = 1;
            q.push(p[x]);
            ans1--;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            int len = 0;
            bool flag = 0;
            for (int j = i; !st[j]; j = p[j])
            {
                len++;
                flag |= vis[j];
                st[j] = 1;
            }
            ans1 -= len / 2;
            ans2 -= (flag ^ 1) && (len != 1);
        }
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}