Author: Maaz Bin Asad
Tester: Prasoon Jain
Editorialist: Maaz Bin Asad
DIFFICULTY
Medium
PREREQUISITES
Graphs, Depth First Search
PROBLEM:
You are given n computers and a file. You need to make all computers access the file. A computer can access the file if it has the file installed or some other computer in the same connected component has the file. The price of connecting any two computers and installing the file are given. You can only connect computers with same protocol. Find minimum price to make the file accessible to all computers.
Quick Explanation:
Count number of computers in a connected component. Either give file to each computer in this component or give the file to only one of them and connect all these computers with minimum edges. Repeat for all connected components.
Explanation:
We can run a DFS to count number of computers in current connected component. Suppose, there are m computers in some arbitrary connected component. Minimum edges to connect m nodes would be m-1. Then, the price of giving access to all computers is minimum of (m-1)xprice of connecting any two computers + price of installing the file and m x price of installing the file. Repeat this process in all connected components.
TIME COMPLEXITY:
O(V+E) per test case.
SOLUTIONS:
Setter’s solution:
#pragma GCC optimize("O2")
#include<iostream>
#include<algorithm>
#include<limits>
#include <cmath>
#include<unordered_map>
#include<vector>
#include<unordered_set>
#pragma warn -rvl #pragma warn -par #pragma warn -rch
#define pb push_back
#define all(r) r.begin(),r.end()
#define f first
#define s second
#define um unordered_map
#define pi pair<int,int>
#define vi vector<int>
#define mod 1000000007
typedef long long int ll; typedef long int li;
using namespace std;
vi adj[100001];
int vis[100001];
li test;
int n,m,cf,cc,num;
void dfs(int node){
vis[node]=1;
num++;
for(auto ch:adj[node]){
if(vis[ch]==0){
dfs(ch);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>test;
while(test--){
cin>>n>>m>>cf>>cc;
for(int i=1;i<=n;i++){
adj[i].clear();
vis[i]=0;
}
while(m--){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
ll ans=0;
int r,l;
for(int i=1;i<=n;i++){
if(vis[i]==0){
num=0;
dfs(i);
r=(num-1)*cc+cf;
l=num*cf;
ans=ans+min(r,l);
}
}
cout<<ans<<"\n";
}
}
Tester’s solution:
import java.util.ArrayList;
import java.util.ArrayList;
import java.util.Scanner;
class LocalAreaNtwk {
static int cnt=0;
static void dfs(int i,ArrayList<ArrayList<Integer>> ar,boolean vis[]) {
vis[i]=true;
cnt++;
for(int j:ar.get(i)) {
if(!vis[j]) {
dfs(j,ar,vis);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t>0) {
int n=sc.nextInt();
int m=sc.nextInt();
int a=sc.nextInt();
int b=sc.nextInt();
ArrayList<ArrayList<Integer>> ar = new ArrayList<>();
for(int i=0;i<=n;i++) {
ar.add(new ArrayList<>());
}
for(int i=0;i<m;i++) {
int x=sc.nextInt();
int y=sc.nextInt();
ar.get(x).add(y);
ar.get(y).add(x);
}
boolean vis[]=new boolean[n+1];
long ans=0L;
for(int i=1;i<=n;i++) {
cnt=0;
if(!vis[i]) {
dfs(i, ar, vis);
ans=ans+Math.min((cnt-1)*b+a, cnt*a);
}
}
System.out.println(ans);
t--;
}
}
}