题目:花费最少逮老鼠
分析:每个出度为0的强连通分量放置捕鼠器。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <string> 5 #include <map> 6 #include <set> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #include <unordered_map> 11 #include <unordered_set> 12 #include <climits> 13 #include <cmath> 14 #include <functional> 15 #include <numeric> 16 using namespace std; 17 using LL = long long; 18 #define ph emplace_back 19 #define vi vector<int> 20 #define vb vector<bool> 21 #define vvi vector<vector<int>> 22 int main(void){ 23 ios::sync_with_stdio(false); 24 cin.tie(0); 25 int n, num = 0, cnt = 0; 26 cin>>n; 27 vvi g(n+1); 28 vi dfn(n+1), low(n+1), c(n+1)/*每个点属于哪个连通分量*/; 29 vi dout(n+1), w(n+1);//强连通分量的出度 30 vi miv(n+1, 1e9); 31 vb ins(n+1); 32 vvi e; 33 for(int i=1; i<=n; i++)cin>>w[i]; 34 for(int i=1, x; i<=n; i++){ 35 cin>>x; 36 g[i].ph(x); 37 e.ph(vi {i, x}); 38 } 39 stack<int> stk; 40 function<void(int)> tarjan = [&](int u){ 41 dfn[u] = low[u] = ++num; 42 stk.push(u), ins[u] = true; 43 for(auto &j : g[u]){ 44 if(!dfn[j]){ 45 tarjan(j); 46 low[u] = min(low[u], low[j]); 47 }else if(ins[j]){ 48 low[u] = min(low[u], dfn[j]); 49 } 50 } 51 if(dfn[u] == low[u]){ 52 ++cnt; 53 int z; 54 do{ 55 z = stk.top(); 56 ins[z] = false; 57 c[z] = cnt; 58 miv[cnt] = min(miv[cnt], w[z]); 59 stk.pop(); 60 }while(z != u); 61 } 62 }; 63 for(int i=1; i<=n; i++){ 64 if(!dfn[i])tarjan(i); 65 } 66 for(auto& x: e){ 67 int u = x[0], v = x[1]; 68 // cout<<u <<' '<<v<<'\n'; 69 if(c[u]!=c[v])dout[c[u]]++; 70 } 71 int res = 0; 72 for(int i=1; i<=cnt; i++){ 73 if(!dout[i])res += miv[i]; 74 } 75 cout<<res<<'\n'; 76 return 0; 77 }
标签:cnt,CF1027D,int,vi,Hunt,dfn,low,include,Mouse From: https://www.cnblogs.com/Hibert/p/16586644.html