Codeforces Round 895 (Div. 3)F

短命女 2024-03-08 08:42 85阅读 0赞

[Problem - F - Codeforces][]

### F. Selling a Menagerie ###

由题意知，一个动物如果其害怕的动物还没有被买出，就可以卖出翻倍的金币，将点进行拓扑排序，可以先将环外的点卖出，留下环，然后找到环中的（卖价）最小的点让其最后卖

![cb7437799b9243fb945bb9a7df4546cf.jpeg][]

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    bool solve()
    {
    	queue<int> q;
    	int n, a[N], c[N], d[N], ans[N];
    	bool v[N];
    	cin >> n;
    	for(int i = 1; i <= n ; i ++)
    	{
    		d[i] = 0;
    		ans[i] = 0;
    		v[i] = false;
    	}
    	for(int i = 1; i <= n ; i ++)
    	{
    		cin >> a[i];
    		d[a[i]] ++;
    	}
    	for(int i = 1; i <= n; i ++)cin >> c[i];
    	for(int i = 1; i <= n; i ++)
    	{
    		if(d[i] == 0)q.push(i);
    	}
    	int cnt = 0;
    	while(q.size())
    	{
    		//将环外的动物先加入 
    		int k = q.front();
    		q.pop();
    		ans[++ cnt] = k;
    		v[k] = true;
    		d[a[k]] --;
    		if(d[a[k]] == 0)q.push(a[k]);
    	}
    	for(int i = 1; i <= n; i ++)
    	{	 
    		if(v[i] == false)
    		{
    			//循环找到环里价格最小的动物 
    			int k = a[i];
    			int minn = i;
    			while(k != i)
    			{
    				if(c[k] < c[minn])minn = k;
    				k = a[k];
    			}
    			//从最小的动物的前一个点开始每次找前一个点，最后找到的实则就是环中最小的动物  
    			int u = a[minn];
    			while(v[u] == false)
    			{
    				ans[++ cnt] = u;
    				v[u] = true;
    				u = a[u];
    			}
    		}
    	}
    	for(int i = 1; i <= cnt; i ++)cout << ans[i] << ' ';
    	cout << '\n';
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int t;
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1872/problem/F
[cb7437799b9243fb945bb9a7df4546cf.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/a6b9009ec0c5467b8025069773a475a2.png