我怎么连找环都不会 题解 # 不论从哪开始,最终都会陷入循环(包括自环),所以把陷阱放在环上永远是最优的。所以这个题就是要找到所有环然后找出每个环上的最小花费。 找环应该算是比基础的技巧了,但我是第一次遇到这种题(太菜了)。可以在这学如何找环。 Code # #include <bits/stdc++.h> #define forn(i, n) for (int i = 0; i < int(n); ++i) #define for1(i, n) for (int i = 1; i <= int(n); ++i) #define fore(i, l, r) for (int i = int(l); i <= int(r); ++i) #define ford(i, n) for (int i = int(n)-1; i >= 0; --i) #define pb push_back #define eb emplace_back #define ms(a, x) memset(a, x, sizeof(a)) #define F first #define S second #define endl '\n' #define all(x) (x).begin(),(x).end() #define de(x) cout<<#x<<" = "<<(x)<<endl #define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl; using namespace std; typedef long long ll; typedef pair<int, int> pii; constexpr int INF = 0x3f3f3f3f; mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count()); vector<int> a; vector<int> vis; vector<vector<int>> cycles; vector<int> fa; void dfs(int u){ vis[u]=1; int to=a[u]; if(vis[to]==1){ cycles.pb({to}); for(int id=u;id!=to;id=fa[id]) cycles.back().pb(id); }else if(vis[to]==0){ fa[to]=u; dfs(to); } vis[u]=2; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int> cost(n); a=vis=fa=vector<int>(n); for(auto& it:cost ) cin>>it; for(auto& it:a) cin>>it,it--; forn(i,n){ if(vis[i]==0) dfs(i); } ll ans=0; for(auto& cycle:cycles){ int mn=INF; for(auto it:cycle) mn=min(mn,cost[it]); ans+=mn; } cout<<ans; return 0; }