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

二分图一遍就好了。
根据题意可知，

a_i

和

i

是矛盾关系。如果第

i

只生物是天使，那么

a_i

生物就是恶魔；如果第

i

只生物是恶魔，那么

a_i

生物就是天使，用二分图染色。
因为这题图不连通，要求出恶魔数量最多的方案，所以每个连通块选择颜色最多的那个颜色加到答案上。
输出切记换行。注意建双向边，空间开两倍。

CPP

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

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

文章操作

相关推荐

评论

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