fork download
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define endl "\n"
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define ub upper_bound
  7. #define ump unordered_map
  8. #define yes cout<<"YES"<<"\n"
  9. #define no cout<<"NO"<<"\n"
  10. const ll M = 998244353;
  11. const ll N = 2e5 + 10;
  12. const ll INF = 1e9+7;
  13. const int dx[] = {-1, 1, 0, 0};
  14. const int dy[] = {0, 0, -1, 1};
  15. using namespace std;
  16.  
  17.  
  18. vector<ll> graph[N];
  19. ll visited[N];
  20.  
  21. void reset() {
  22. for(ll i = 0; i < N; i++) {
  23. graph[i].clear();
  24. visited[i] = 0;
  25. }
  26. }
  27.  
  28. ll dfs(ll vertex) {
  29. visited[vertex] = 1;
  30. ll ct = 1;
  31. for(ll child : graph[vertex]) {
  32. if(visited[child]) continue;
  33. ct += dfs(child);
  34. }
  35. return ct;
  36. }
  37.  
  38. int main() {
  39. ios_base::sync_with_stdio(false);
  40. cin.tie(0);
  41. ll t; cin >> t;
  42. while(t--) {
  43. reset();
  44. ll n, m, l, r; cin >> n >> m >> l >> r;
  45. for(ll i = 0; i < m; i++) {
  46. ll v1, v2;
  47. cin >> v1 >> v2;
  48. graph[v1].pb(v2);
  49. graph[v2].pb(v1);
  50. }
  51. ll cost = 0;
  52. for(ll i = 1; i <= n; i++) {
  53. if(!visited[i]) {
  54. ll num = dfs(i);
  55. ll need = l + r*(num-1);
  56. cost += need;
  57. }
  58. }
  59. cout<<min(n*l, cost)<<endl;
  60. }
  61. }
Success #stdin #stdout 0.01s 9828KB
stdin
2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6
stdout
4
12