题解：CF2044G2 Medium Demon Problem (hard version)

拓扑排序加一点点树结构。

首先是思路。

事实上，无论这个环到底是什么样子、到底有几个，想要有解，环上所有结点的玩具数就必须相等。也就是说，从出题数据确定的那一刻开始，环的结局就已经确定了。所以我们只需要考虑环外的结点即可。

可以通过拓扑排序找到所有的环外结点。可以确定的是，因为它们在环外，它们肯定会呈现出一个或多个树形图结构。我们要做的，就是将这些树的根结点找出来一一比较，玩具最多的那个根结点，就是我们需要的答案。

请注意，根结点的玩具数等于所有子树的和加上本身初始状态的一，也就是这棵树的玩具总数。

CPP

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
//对应数组分别为：路径、入度、礼物个数
int T, N, arr[200010], f[200010], sum[200010], S, n, temp, ans;
vector<int>V;//存储非环结点
queue<int>Q;//筛选非环结点
//4 1 1 5 4
int main()
{
	std::ios::sync_with_stdio(false);
	cin >> T;
	while (T--) {
		cin >> N;
		ans = 0; 
		for (int i = 1; i <= N; i++) {
			cin >> arr[i];
			f[arr[i]]++, sum[i] = 1;//入度、玩具初始化
		}
		
		for (int i = 1; i <= N; i++) {
			if (f[i] == 0)Q.push(i),V.push_back(i);//第一批入度为零的结点入队，同时也是非环结点
		}
		while (!Q.empty()) {//拓扑排序，挑选所有非环结点
			temp = Q.front();
			Q.pop();
			f[arr[temp]]--;
			if (f[arr[temp]] == 0)Q.push(arr[temp]),V.push_back(arr[temp]);
		}

		for (auto t : V) {//将所有非环结点的玩具数分发下去
			sum[arr[t]] += sum[t];
		}
		for (auto t : V) {//统计拥有最多玩具的结点
			ans=max(ans,sum[t]);
		}
		
		//善后工作
		V.clear();
		for (int i = 1; i <= N; i++) {
			arr[i] = 0, f[i] = 0, sum[i] = 0;
		}
		cout << ans+2 << '\n';//从第二年开始，记得加2
	}
	return 0;
}

题解：CF2044G2 Medium Demon Problem (hard version)

文章操作

相关推荐

评论

题解：CF2044G2 Medium Demon Problem (hard version)