PROBLEM LINK:Contest Page | CodeChef
Author: Udit Garg
Tester: Udit Garg
Editorialist: Udit Garg
DIFFICULTY:
MEDIUM
PREREQUISITES:
Graphs, DFS
PROBLEM:
In a computer lab there are N computers. Computers are interconnected with each other through M wires. Each wire gives a two-way path. Two computers are said to be in network if there is simple path from one computer to another computer through these wires. You need to install antivirus to each computer. If one antivirus is installed on one computer then it will automatically get installed on all computers connected on a network with that computer. Before starting installing antivirus, you can connect two computers by buying one wire. Also, you need to buy required amount of antivirus. There is infinite supply of antivirus and wires. One antivirus cost A rupees and One wire cost B rupees. Find out minimum money required so that all computers are protected by antivirus.
EXPLANATION:
Editorial
In this problem, consider computers as Nodes of graph and wires as undirected edges connecting two vertices. So, we can say that we are given an unweighted undirected graph with N nodes and M edges. To make all computers protected by antivirus, we need at least 1 antivirus. If given graph is connected then answer simply will be A i.e. cost of one antivirus. If our graph is disconnected, we need to either connect it by buying wires or we need to buy separate antivirus for each disconnect component of graph. Firstly, find number of components of graph using dfs(Depth first search). Let us assume there are cnt components. Now we need either cnt antivirus or one antivirus along with cnt-1 wires. To find minimum cost approach out of them , we just have to calculate min(cntA,A+B(cnt-1).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define MaxN 10005
using namespace std;
vector graph[MaxN];
bool visited[MaxN];
void dfs(int u)
{
visited[u]=true;
for(auto i:graph[u])
{
if(!visited[i])
dfs(i);
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n,m,a,b;
cin>>n>>m>>a>>b;
for(int i=1;i<=n;i+=1)
visited[i]=false;
for(int i=0;i<m;i+=1)
{
int x,y;
cin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
int cnt=0;
for(int i=1;i<=n;i+=1)
{
if(!visited[i])
{
dfs(i);
cnt+=1;
}
}
cout<<min(acnt,a+b(cnt-1));
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define MaxN 10005
using namespace std;
vector graph[MaxN];
bool visited[MaxN];
void dfs(int u)
{
visited[u]=true;
for(auto i:graph[u])
{
if(!visited[i])
dfs(i);
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n,m,a,b;
cin>>n>>m>>a>>b;
for(int i=1;i<=n;i+=1)
visited[i]=false;
for(int i=0;i<m;i+=1)
{
int x,y;
cin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
int cnt=0;
for(int i=1;i<=n;i+=1)
{
if(!visited[i])
{
dfs(i);
cnt+=1;
}
}
cout<<min(acnt,a+b(cnt-1));
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
#define MaxN 10005
using namespace std;
vector graph[MaxN];
bool visited[MaxN];
void dfs(int u)
{
visited[u]=true;
for(auto i:graph[u])
{
if(!visited[i])
dfs(i);
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n,m,a,b;
cin>>n>>m>>a>>b;
for(int i=1;i<=n;i+=1)
visited[i]=false;
for(int i=0;i<m;i+=1)
{
int x,y;
cin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
int cnt=0;
for(int i=1;i<=n;i+=1)
{
if(!visited[i])
{
dfs(i);
cnt+=1;
}
}
cout<<min(acnt,a+b(cnt-1));
return 0;
}