CodeForces 1027D - Mouse Hunt

我怎么连找环都不会

题解 #

不论从哪开始,最终都会陷入循环(包括自环),所以把陷阱放在环上永远是最优的。所以这个题就是要找到所有环然后找出每个环上的最小花费。

找环应该算是比基础的技巧了,但我是第一次遇到这种题(太菜了)。可以在这学如何找环。

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;
}