fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. template<typename T>
  17. void minimize(T& a, const T& b) {
  18. 	if (b < a) a = b; 
  19. }
  20.  
  21. // Ta sẽ nén mỗi thành phần liên thông mạnh thành 1 đỉnh
  22. // Đồ thị sau khi nén G' sẽ là một DAG (đồ thị có hướng không có chu trình)
  23. // Từ đây đưa về bài toán tìm đường đi dài nhất (đường đi có tổng lớn nhất) trên DAG
  24. // => DP trên DAG
  25. const int N = 1e5 + 5; 
  26.  
  27. int n, m; 
  28. int a[N]; 
  29. vector<int> adj[N]; 
  30.  
  31. int num_scc;   
  32. int tin[N], low[N], timer;   
  33. int id[N]; 
  34. vector<int> st;  
  35. bool in_stack[N];
  36.  
  37. ll sum[N]; // sum[i]: tổng a(u) của các đỉnh u thuộc thành phần liên thông mạnh thứ i
  38.  
  39. void dfs(int u) {
  40. 	tin[u] = low[u] = ++timer;   
  41. 	st.push_back(u);  
  42. 	in_stack[u] = true;  
  43.  
  44. 	for (int v : adj[u]) {
  45. 		if (!tin[v]) {
  46. 			dfs(v); 
  47. 		}
  48. 		if (in_stack[v]) {
  49. 			minimize(low[u], low[v]); 
  50. 		}
  51. 	}
  52.  
  53. 	if (low[u] == tin[u]) {
  54. 		num_scc++;  
  55. 		while (true) {
  56. 			int v = st.back(); st.pop_back(); 
  57. 			in_stack[v] = false; 
  58. 			id[v] = num_scc;  
  59. 			sum[num_scc] += a[v]; 
  60. 			if (v == u) break; 
  61. 		}
  62. 	}
  63. }
  64.  
  65. vector<int> g[N]; // Danh sách kề của đồ thị sau khi nén
  66.  
  67. // dp(u) = Đường đi dài nhất xuất phát tại u 
  68. ll memo[N];  
  69.  
  70. ll dp(int u) {
  71. 	ll& ans = memo[u]; 
  72. 	if (ans != -1) return ans;  
  73.  
  74. 	ans = sum[u];   
  75. 	for (int v : g[u]) {
  76. 		maximize(ans, sum[u] + dp(v)); 
  77. 	}
  78.  
  79. 	return ans; 
  80. }
  81.  
  82. int main() {
  83. 	ios::sync_with_stdio(false); 
  84. 	cin.tie(nullptr); 	
  85. 	cin >> n >> m; 
  86. 	for (int u = 1; u <= n; u++) cin >> a[u]; 
  87.  
  88. 	for (int i = 0; i < m; i++) {
  89. 		int u, v; 
  90. 		cin >> u >> v; 
  91. 		adj[u].push_back(v); 
  92. 	}
  93.  
  94. 	num_scc = 0;   
  95. 	timer = 0; 
  96. 	for (int u = 1; u <= n; u++) {
  97. 		if (!tin[u]) dfs(u); 
  98. 	}
  99.  
  100. 	for (int u = 1; u <= n; u++) {
  101. 		for (int v : adj[u]) {
  102. 			if (id[u] == id[v]) continue;  
  103. 			g[id[u]].push_back(id[v]); 
  104. 		}
  105. 	}
  106.  
  107. 	memset(memo, -1, sizeof memo);  
  108.  
  109. 	ll ans = 0; 
  110. 	for (int u = 1; u <= num_scc; u++) {
  111. 		maximize(ans, dp(u)); 
  112. 	}
  113.  
  114. 	cout << ans << '\n'; 
  115. }
Success #stdin #stdout 0.01s 11352KB
comments (?)
stdin
copy 
4 4
4 5 2 7
1 2
2 1
1 3
2 4
stdout
copy 
16
https://ideone.com/TPDRev
language:
C++14 (gcc 8.3)
created:
259 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!