Untitled
unknown
plain_text
a year ago
1.3 kB
6
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define endl "\n" const double PI = 3.14159265358979; const ll INF = 1e18 + 7; const ll MOD = 1e9 + 7; const ll nax = 2505; const int LOG = 25; int getComponentSize(int src, int par, vector<int> adj[], vector<bool> &vis) { vis[src] = true; int cnt = 1; for (int v : adj[src]) { if (v == par) continue; if (!vis[v]) { cnt += getComponentSize(v, src, adj, vis); } } return cnt; } void solve() { int n, m, c, r; cin >> n >> m >> c >> r; vector<int> adj[n + 1]; vector<bool> vis(n + 1, false); for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } ll ans = 0; for (int i = 1; i <= n; i++) { if (!vis[i]) { int componentSize = getComponentSize(i, 0, adj, vis); if (r <= c) { ans = ans + 1LL * (componentSize - 1) * r + c; } else { ans = ans + 1LL * componentSize * c; } } } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; while(t--) solve(); return 0; }
Editor is loading...
Leave a Comment