题解：AT_maximum_cup_2018_c 嘘つきな天使たち

wyyinput · 2025-03-06 15:39:09 · 题解

二分图一遍就好了。
根据题意可知，a_i 和 i 是矛盾关系。如果第 i 只生物是天使，那么 a_i 生物就是恶魔；如果第 i 只生物是恶魔，那么 a_i 生物就是天使，用二分图染色。
因为这题图不连通，要求出恶魔数量最多的方案，所以每个连通块选择颜色最多的那个颜色加到答案上。
输出切记换行。注意建双向边，空间开两倍。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1,M=4e5+1;
int n,v,cnt,ans,cnt1,cnt2,head[N],a[N];//a数组用于染色
struct node{
    int to;
    int ne;
}tu[M];
void add(int x,int y){
    tu[++cnt].to=y;
    tu[cnt].ne=head[x];
    head[x]=cnt;
    return;
}
void dfs(int now,int colour){
    for(int i=head[now];i;i=tu[i].ne){
        if(a[tu[i].to]==0){
            if(-colour==1)
                cnt1++;
            else
                cnt2++;
            a[tu[i].to]=-colour;
            dfs(tu[i].to,-colour);
        }
        else if(a[tu[i].to]==-colour){
            continue;
        }
        else{
            puts("-1");
            exit(0);
        }
    }
    return;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&v);
        add(i,v);
        add(v,i);
    }
    for(int i=1;i<=n;i++){
        if(!a[i]){
            a[i]=1;
            cnt1=1;
            cnt2=0;
            dfs(i,1);
            ans+=max(cnt1,cnt2);
        }
    }
    printf("%d",ans);
    return 0;
}