fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, M, K, desa[100001];
  5. vector<int> adjList[100001];
  6. bool visited[100001];
  7.  
  8. int dfs(int node) {
  9. 	visited[node] = true;
  10. 	int ans = desa[node];
  11. 	for(int i = 0; i < adjList[node].size(); i++)
  12. 		if(!visited[adjList[node][i]])
  13. 			ans = min(ans, dfs(adjList[node][i]));
  14. 	//for(auto it = adjList[node].begin(); it != adjList[node].end(); it++)
  15. 	//	if(!visited[*it])
  16. 	//		dfs(*it);
  17. 	return ans;
  18. }
  19.  
  20. int main() {
  21. 	cin >> N >> M >> K;
  22. 	vector<int> sulit, tarif(M);
  23. 	for(int i = 0; i < N; i++)
  24. 		cin >> desa[i];
  25. 	for(int i = 0; i < M; i++)
  26. 		cin >> tarif[i];
  27. 	for(int i = 0; i < K; i++) {
  28. 		int a, b;
  29. 		cin >> a >> b;
  30. 		a--; b--;
  31. 		adjList[a].push_back(b);
  32. 		adjList[b].push_back(a);
  33. 	}
  34. 	memset(visited, false, sizeof(visited));
  35. 	for(int i = 0; i < N; i++)
  36. 		if(!visited[i]) {
  37. 			int ans = dfs(i);
  38. 			sulit.push_back(ans);
  39. 			// cout << i+1 << " " << ans << endl;
  40. 		}
  41. 	if(sulit.size() > tarif.size())
  42. 		cout << -1 << endl;
  43. 	else {
  44. 		int total = 0, size = sulit.size();
  45. 		sort(sulit.begin(), sulit.end());
  46. 		sort(tarif.begin(), tarif.end());
  47. 		for(int i = 0; i < size; i++)
  48. 			total += sulit[i]*tarif[size-1-i];
  49. 		cout << total << endl;
  50. 	}
  51. 	return 0;
  52. }
Success #stdin #stdout 0.01s 6120KB
comments (?)
stdin 
8 4 5
7 5 3 10 2 8 6 9
25 10 35 30
1 2
3 4
5 4
4 6
3 5
stdout 
460
https://ideone.com/ImD35l
language:
C++ (gcc 8.3)
created:
15 days ago
visibility:
public

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!