Educational Codeforces Round 49 D Mouse Hunt
前回のままではさすがに芸が無いからsccの応用問題を解いてみたよ
Problem - 1027D - Codeforces
強連結成分分解→強連結成分どうしの隣接リストを作ってdfsの流れで
#include<cstdio> #include<vector> #include<algorithm> #include<climits> using namespace std; static const int MAX_N = 200000; int N; int c[MAX_N], a[MAX_N]; vector<int> G[MAX_N]; vector<int> rG[MAX_N]; vector<int> vs; bool used[MAX_N]; int cmp[MAX_N]; vector<int> G2[MAX_N]; int num[MAX_N]; bool visited[MAX_N]; void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } void dfs(int v){ used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(!used[G[v][i]]) dfs(G[v][i]); } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for(int i = 0; i < rG[v].size(); i++){ if(!used[rG[v][i]]) rdfs(rG[v][i], k); } } int scc(){ fill(used, used + N, false); vs.clear(); for(int i = 0; i < N; i++){ if(!used[i]) dfs(i); } fill(used, used + N, false); int k = 0; for(int i = vs.size() - 1; i >= 0; i--){ if(!used[vs[i]]) rdfs(vs[i], k++); } return k; } int dfs2(int s){ if(visited[s]) return 0; visited[s] = true; if(G2[s].size() == 0) return num[s]; int res = 0; for(int i = 0; i < G2[s].size(); i++){ if(visited[G2[s][i]]) continue; res += dfs2(G2[s][i]); } return res; } int main(){ scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d", &c[i]); for(int i = 0; i < N; i++){ scanf("%d", &a[i]); a[i]--; if(i == a[i]) continue; add_edge(i, a[i]); } int n = scc(); fill(num, num + n, INT_MAX); fill(visited, visited + n, false); for(int i = 0; i < N; i++){ num[cmp[i]] = min(num[cmp[i]], c[i]); if(cmp[i] == cmp[a[i]]) continue; G2[cmp[i]].push_back(cmp[a[i]]); } int res = 0; for(int i = 0; i < n; i++){ res += dfs2(i); } printf("%d\n", res); return 0; }