题意：给定n个房间，有一只老鼠可能从其中的任意一个出现，
在第i个房间设置捕鼠夹的代价是a[i]，若老鼠当前在i号房间则下一秒会移动到b[i]号，
问一定能抓住老鼠的最小的总代价
n<=2e5，a[i]<=1e4
思路：tarjan缩点（环）之后找到所有出度为0的分量，找到分量中最小的a[i]，将a[i]加到ans中
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 #include<bitset> 12 using namespace std; 13 typedef long long ll; 14 typedef unsigned int uint; 15 typedef unsigned long long ull; 16 typedef pair<int,int> PII; 17 typedef vector<int> VI; 18 #define fi first 19 #define se second 20 #define MP make_pair 21 #define N 210000 22 #define M 51 23 #define MOD 1000000007 24 #define eps 1e-8 25 #define pi acos(-1) 26 #define oo 1e9 27 28 int flag[N],dfn[N],low[N],a[N],b[N],s[N],f[N],stk[N],oud[N],top,tim,id; 29 vector<int>c[N]; 30 31 void dfs(int u) 32 { 33 flag[u]=1; 34 stk[++top]=u; 35 dfn[u]=low[u]=++tim; 36 for(int i=0;i<=(int)c[u].size()-1;i++) 37 { 38 int v=c[u][i]; 39 if(!flag[v]) 40 { 41 dfs(v); 42 low[u]=min(low[u],low[v]); 43 } 44 else if(!s[v]) low[u]=min(low[u],low[v]); 45 } 46 if(low[u]==dfn[u]) 47 { 48 id++; 49 while(stk[top]!=u) 50 { 51 s[stk[top]]=id; 52 top--; 53 } 54 s[stk[top]]=id; 55 top--; 56 } 57 } 58 59 int main() 60 { 61 int n; 62 scanf("%d",&n); 63 id=0; 64 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 65 for(int i=1;i<=n;i++) 66 { 67 scanf("%d",&b[i]); 68 c[i].push_back(b[i]); 69 } 70 tim=0; 71 for(int i=1;i<=n;i++) 72 if(!flag[i]) dfs(i); 73 int ans=0; 74 for(int i=1;i<=id;i++) f[i]=oo; 75 for(int i=1;i<=n;i++) f[s[i]]=min(f[s[i]],a[i]); 76 for(int i=1;i<=n;i++) if(s[i]!=s[b[i]]) oud[s[i]]++; 77 for(int i=1;i<=id;i++) 78 if(!oud[i]) ans+=f[i]; 79 printf("%d ",ans); 80 return 0; 81 }