题目：

伯兰州立大学的医学部刚刚结束了招生活动。和以往一样，约80%的申请人都是女生并且她们中的大多数人将在未来4年（真希望如此）住在大学宿舍里。

宿舍楼里有nn个房间和一只老鼠！女孩们决定在一些房间里设置捕鼠器来除掉这只可怕的怪物。在ii号房间设置陷阱要花费c_ic
i
​ 伯兰币。房间编号从11到nn。

要知道老鼠不是一直原地不动的，它不停地跑来跑去。如果tt秒时它在ii号房间，那么它将在t+1t+1秒时跑到a_ia
i
​ 号房间，但这期间不会跑到别的任何房间里(i=a_ii=a
i
​ 表示老鼠没有离开原来的房间)。时间从00秒开始，一旦老鼠窜到了有捕鼠器的房间里，这只老鼠就会被抓住。

如果女孩们知道老鼠一开始在哪里不就很容易吗？不幸的是，情况不是这样，老鼠在第00秒时可能会在从11到nn的任何一个房间内。

那么女孩们最少要花多少钱设置捕鼠器，才能保证老鼠无论从哪个房间开始流窜最终都会被抓到？

分析：

stack解决

a向a[x]连边

代码：

#include<cstdio> #include<stack> using namespace std; int a[200005]; int cnt=0; int vis[200005],c[200005]; int flag; int tag; stack<int>s; void dfs(int x) { if(a[x]==0) { return ; } cnt++; if(cnt>vis[x]&&vis[x]) { flag=1; tag=x; a[x]=0; vis[x]=0; return ; } s.push(x); vis[x]=cnt; dfs(a[x]); vis[x]=0; a[x]=0; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&c[i]); } for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } int sum=0; for(int i=1;i<=n;i++) { while(!s.empty())s.pop(); flag=0; dfs(i); if(flag) { int ans=2147483647; if(!s.empty()) { while(!s.empty()&&s.top()!=tag) { ans=min(ans,c[s.top()]); s.pop(); } if(!s.empty()) ans=min(ans,c[s.top()]); sum+=ans; } } } printf("%d\n",sum); return 0; }