CF1027D Mouse Hunt
starseven
2020-06-05 20:08:16
[同步于我的博客](https://www.cnblogs.com/starseven/p/13052121.html)
[题目链接](https://codeforces.com/problemset/problem/1027/D)
[luogu链接](https://www.luogu.com.cn/problem/CF1027D)
这道题的简略题意是:
有一个$n$个点，$n$条边的有向图（可能有自环和重边），叫我们以最小代价选取一些点，使得无论从哪个点出发都要经过这些点。
思路：
因为有n个点，n条边，所以说我们可以知道一定至少有一个环。
而对于一条链来说，这条链必然要通向一个环！
所以我们就可以先进行topo排序，将所有的链删去，然后进行dfs来寻找环内的最大值！
$$ Talk \;is\;cheap,\;show\;the\;code\;!$$
```cpp
#include<cstdio>
#include<iostream>
#define ri register int
#define Starseven main
using namespace std;
const int N=2e5+20;
int n,m,cost[N],ans=0,k,to[N],du[N];
bool vis[N];
void Topo(int x){
vis[x]=true;
du[to[x]]--;
if(!du[to[x]]) Topo(to[x]);
}
int Dfs(int x){
vis[x]=true;
if(!vis[to[x]]) return min(Dfs(to[x]),cost[x]);
else return cost[x];
}
int Starseven(void){
cin>>n;
for(ri i=1;i<=n;i++) cin>>cost[i];
for(ri i=1;i<=n;i++){
int x;cin>>x;
to[i]=x,du[x]++;
}
for(ri i=1;i<=n;i++) if(!du[i]&&!vis[i]) Topo(i);
for(ri i=1;i<=n;i++) if(!vis[i]) ans+=Dfs(i);
cout<<ans<<endl;
return 0;
}
```