该题考察了拓扑排序+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;
}