P6417 [COCI 2014/2015 #1] MAFIJA

题目描述

有 $n$ 个人，其中有一些人是平民，有一些人是坏蛋。

现在，平民们想揪出所有的坏蛋，于是 $n$ 个人都指认了一个人是坏蛋。

如果一个人是平民，他会随便乱指认，否则，他会指认一个平民。

求出最多的坏蛋个数。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个整数 $k$，第 $i$ 行表示第 $i$ 个人指认了第 $k$ 个人。

输出格式

仅一行一个整数，表示最多的坏蛋个数。

输入输出样例 #1

输入 #1

3
2
1
1

输出 #1

2

输入输出样例 #2

输入 #2

3
2
3
1

输出 #2

1

输入输出样例 #3

输入 #3

7
3
3
4
5
6
4
4

输出 #3

4

说明/提示

样例解释

样例输入输出 1 解释

坏蛋可以是第 $2$ 个人和第 $3$ 个人。

样例输入输出 2 解释

坏蛋可能是所有人，但是只能是其中的一个人，因为再多一个坏蛋的话会有坏蛋指控坏蛋的情况发生。

数据范围与限制

• 对于 $40$ 分的数据，保证 $n\le 15$。
• 对于 $80$ 分的数据，保证 $n\le 2\times 10^4$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$1\le k\le n$。

说明

本题总分 $120$ 分。

本题译自 Croatian Open Competition in Informatics 2014/2015 Contest #1 T4 MAFIJA。

C++实现

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std ;
const int N = 5e5 + 5 ;
int n, res, in[N], to[N] ;
bool color[N] ;
void dfs(int u, bool cur)
{
	if (color[u]) return ;
	
	color[u] = 1, res += cur ;
	if (! -- in[to[u]] || cur)
		dfs(to[u], !cur) ;
}
int main()
{
	ios::sync_with_stdio(false) ;
	
	cin >> n ;
	for (int i = 1 ; i <= n ; i ++ )
		cin >> to[i], in[to[i]] ++  ;
	
	for (int i = 1 ; i <= n ; i ++ )
		if (!in[i]) dfs(i, true) ;
	for (int i = 1 ; i <= n ; i ++ )
		dfs(i, false) ;
	
	cout << res << '\n' ;
	
	return 0 ;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容