网站建设免费书免费发广告的软件

该题考察了拓扑排序+dfs

题意：你是一个动物园的主人，该动物园由编号从1到n的n只动物组成。然而，维护动物园是相当昂贵的，所以你决定卖掉它！众所周知，每种动物都害怕另一种动物。更确切地说，动物ii害怕动物ai（ai≠i）。此外，每只动物的成本是已知的，对于动物ii，它等于ci。你会按照固定的顺序卖掉你所有的动物。形式上，您需要选择一些排列†p1，p2，…，pn，然后先出售动物p1，然后出售动物p2，依此类推，最后出售动物pn。当你出售动物ii时

有两种可能的结果：如果动物ai在动物ii之前出售，你将因出售动物ii而获得cici资金。如果动物ai在动物i之前没有被出售，您出售动物i将获得2∙ci的金钱。（令人惊讶的是，目前害怕的动物更有价值）。你的任务是选择出售动物的顺序，以最大限度地提高总利润。多组输入

输入样例

8

3

2 3 2

6 6 1

8

2 1 4 3 6 5 8 7

1 2 1 2 2 1 2 1

5

2 1 1 1 1

9 8 1 1 1

2

2 1

1000000000 999999999

7

2 3 2 6 4 4 3

1 2 3 4 5 6 7

5

3 4 4 1 3

3 4 5 6 7

3

2 1 1

1 2 2

4

2 1 4 1

1 1 1 1

输出样例 

1 2 3
2 4 5 1 6 3 7 8
3 4 5 1 2
1 2
7 5 1 3 2 6 4
5 3 2 4 1
3 2 1
3 4 1 2

思路： 如果该动物害怕的动物已经卖出了 则该动物能获得利润ci 若没有卖出则ci

所以应该尽量让每个动物在它害怕的动物卖出前卖出 即 i在a[i]之前卖出（害怕的动物先卖出）

若该动物没有被任何动物害怕 可以让它们先卖出

同时将这些动物卖出之后，可能又会使得一些动物不被任何动物害怕（可以想象到用拓扑排序）

 比如 a ：2 3 4 5 3，那么动物 1 就没有被任何动物害怕，我们先将它卖出，卖出之后又会使得动物 2 不被任何动物害怕。这个过程可以用拓扑排序实现，相当于连一条 i 到 a[i] 的边，同时记录每个点的入度，入度为 0 时入队即可。

但这个拓扑过程可能并不会包含所有的点，因为有些点之间可能是一个环的关系，就是一个怕一个，形成了个闭环，比如上述例子中的动物 ，，3，4，5 。对于这种环我们拓扑肯定是处理不了的。我们需要考虑打破这个环，使其成为一个有顺序的链，那么很明显我们可以使价格最便宜的动物作为链的末尾，因此我们可以先用一个 dfs 找到这个环中价格最小的动物，然后让它所害怕的动物作为链的起始即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=5e5+10;
int a[N],c[N],d[N],id=-1,mins=0;
bool st[N];
void dfs(int u)
{if(st[u]) return ;st[u]=true;int x=a[u];if(c[x]<mins) mins=c[x],id=x;dfs(x);
}
int main()
{int t;cin>>t;while(t--){memset(st,0,sizeof st);memset(d,0,sizeof d);int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i],d[a[i]]++;for(int i=1;i<=n;i++) cin>>c[i];queue<int>q;vector<int>v;//拓扑排序for(int i=1;i<=n;i++)if(!d[i]) q.push(i);while(q.size()){int t=q.front();q.pop();st[t]=true;v.push_back(t);int x=a[t];d[x]--;if(!d[x]) q.push(x);}for(int i=1;i<=n;i++){//寻找是否有环if(!st[i]){mins=c[i];id=i;dfs(i);int x=a[id];、//用do  while 先运行一次 否则用while根本就不会进去do{v.push_back(x);x=a[x];}while(x!=a[id]);}}for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl;}return 0;
}