F. Selling a Menagerie Codeforces Round 895 (Div. 3)

Problem - F - Codeforces

题目大意：有n个动物，每个动物i有一个害怕的动物a[i]，现要卖掉所有动物，每个动物都有价值c[i]，如果i在a[i]之前卖掉，就会获得2*c[i]的价值，如果在a[i]之后被卖掉就会获得c[i]的价值，问以什么顺序卖掉所有动物能使获得的总价值最高

2<=n<=1e5；1<=ci<=1e9

思路：对于这种约束问题，首先直接从i向a[i]建单向边，初始状态下，所有没有入边的点卖掉都能获得2*c[i]的价值，同时因为该点被删除，所以他们指向的点入度-1，接着卖掉入度为0的点，依次循环，最后一定会出现剩下的点都成环的情况。

对于某一个环，我们最优的方案就是选择一个点留着最后卖，其余的点按照环的方向依次卖，例如题目中的样例5，画出的涂如下，卖的顺序就是1,5,7,3,2,6,4

也就是我们dfs遍历每个环，在环中找出价值最小的那个点，把它放在最后，其余点按环的顺序即可

//#include<__msvc_all_public_headers.hpp>
#include
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int n;
paira[N];
int to[N];
int d[N];
bool vis[N];
ll c[N];
void init()
{
	for (int i = 1; i <= n; i++)
	{
		d[i] = 0;
		vis[i] = 0;
	}
}
ll mi, mii;
void dfs(int u)
{//遍历环
	int v = to[u];
	if (c[u] < mi)
	{
		mi = c[u];
		mii = u;
	}//找到环中价值最小的点
	vis[u] = 1;
	if (!vis[v])
	{
		dfs(v);
	}
}
void solve()
{
	cin >> n;
	init();
	for (int i = 1; i <= n; i++)
	{
		int v;
		cin >> v;
		to[i] = v;//建有向边
		d[v]++;//记录入度
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i];
	}
	queue<int>q;
	vector<int>ans;
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{//将初始入度为0的先卖掉
			q.push(i);
			vis[i] = 1;
		}
	}
	while (!q.empty())
	{//先处理环外的点
		int u = q.front();
		q.pop();
		ans.push_back(u);
		int v = to[u];
		d[v]--;//类似于拓扑排序的操作
		if (!d[v])
		{
			vis[v] = 1;
			q.push(v);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			mi = 1e9 + 1;
			dfs(i);
			int now = to[mii];//从价值最小的点的下一个点开始沿着环卖
			while (now != mii)
			{
				ans.push_back(now);
				now = to[now];
			}
			ans.push_back(mii);
		}
	}
	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i] << " ";
	}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}