题解 P6417 【[COCI2014-2015#1] MAFIJA】

Randyhoads · 2020-10-23 15:23:15 · 题解

更好的体验？

贪心

把指认的关系当做边连边，把坏蛋当做染成1，好人当做染成0

由于坏蛋不能连坏蛋，与1相连的点一定为0

假如是一条链的话，显然交叉染色，从链尾开始染更优

把链扩展成树，发现每次把入度为0的点染成1一定最优

但是实际上有可能出现环

考虑为环的情况，如果环上的点都没有限制，显然随便选一个点染成0，这个点两边染色就没有限制了，就断成链了

考虑环上的点有限制的情况，即为基环树的情况

还是从入度为0的点开始染，环上有点被确定染成了0那么这个环显然就被断成链了，就按找链的方式贪心即可

所以可以设计出这样一个贪心算法

每次把入度为0且没有确定下来的点染成1，这样最后剩下的一定是几个独立的环

每次随便选环上一点染成0，把环断成链即可

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    int f = 1,x = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch == '-') f = -1;
    }while(ch < '0'||ch > '9');
    do
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }while(ch >= '0'&&ch <= '9');
    return f*x;
}

const int MAXN = 5e5 + 10;

int n;
int a[MAXN];
int deg[MAXN]; 
bool vis[MAXN];
int ans;

inline void dfs(int x,int col)
{
    if(vis[x]) return;
    vis[x] = 1; 
    ans += col;
    deg[a[x]]--;
    if((!deg[a[x]])||col == 1) dfs(a[x],col^1);
}

int main()
{
    n = read();
    for(int i=1;i<=n;i++) a[i] = read(),deg[a[i]]++;
    for(int i=1;i<=n;i++) if(!deg[i]) dfs(i,1);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
    cout << ans << endl;
}