HackerRank World CodeSprint 8: Roads and Libraries
solution
Let $K$ be the number of components of given graph, then $\mathrm{ans} = \min \{ k \cdot c_{\mathrm{lib}} + (n-k) \cdot c_{\mathrm{road}} \mid 1 \le k \le K \}$. $O(n)$ for each query.
implementation
#include <iostream>
#include <vector>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
typedef long long ll;
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
const ll inf = ll(1e18)+9;
int main() {
int queries; cin >> queries;
while (queries --) {
int n, m, c_lib, c_road; cin >> n >> m >> c_lib >> c_road;
vector<vector<int> > g(n);
repeat (i,m) {
int u, v; cin >> u >> v; -- u; -- v;
g[u].push_back(v);
g[v].push_back(u);
}
int components = 0; {
vector<bool> used(n);
function<void (int)> dfs = [&](int i) {
used[i] = true;
for (int j : g[i]) if (not used[j]) dfs(j);
};
repeat (i,n) if (not used[i]) {
components += 1;
dfs(i);
}
}
ll ans = inf;
for (int k = components; k <= n; ++ k) { // inefficient
setmin(ans, k *(ll) c_lib + (n-k) *(ll) c_road);
}
cout << ans << endl;
}
return 0;
}