Я реализую алгоритм графа на Hackerrank .
Постановка задачи :
Правитель HackerLand считает, что каждый гражданин страны должен иметь доступ к библиотеке. К сожалению, HackerLand был поражен торнадо, который разрушил все его библиотеки и преградил ему дороги! Поскольку вы - величайший программист HackerLand, правитель хочет, чтобы вы помогли починить дороги и эффективно построить несколько новых библиотек.
HackerLand имеет n городов, пронумерованных от 1 до n. Города соединены двунаправленными дорогами. Гражданин имеет доступ к библиотеке, если:
- В их городе есть библиотека.
- Они могут путешествовать по дороге из своего города в город, содержащий библиотеку.
На следующем рисунке приведен пример карты HackerLand, где пунктирными линиями обозначены загороженные дороги:
Стоимость ремонта любой дороги составляет c_road долларов, а стоимость строительства библиотеки в любом городе составляет c_lib долларов. Если в приведенном выше примере c_road=2 и c_lib=3, мы построим 5 дорог по стоимости 5*2 и 2 библиотек по стоимости 6. Нам не нужно перестраивать одну из дорог в цикле 1->2->3->1.
Вам дано q запросов, где каждый запрос состоит из карты HackerLand и значения c_lib и c_road. Для каждого запроса найдите минимальную стоимость доступа к библиотекам для всех граждан и напечатайте ее на новой строке.
Мой подход:
Я делаю график с указанными городами и дорогами, где каждый город обозначает узел на графике, а каждая дорога обозначает ребро. Я использовал алгоритм BFS, чтобы найти связанные компоненты графа. Затем создайте библиотеку в каждом компоненте и постройте минимальное количество дорог, чтобы компоненты оставались подключенными.
Ответ:
Возврат минимум двух.
- Стоимость создания библиотеки в каждом компоненте + ремонт дорог, чтобы каждый компонент имел минимальное количество дорог.
- Создание библиотеки в каждом городе.
В приведенном выше случае стоимость строительства дороги составляет 2 доллара (c_road=2), а стоимость создания библиотеки - 3 (c_lib=3).
Здесь этот график состоит из двух компонентов: 1,2,3,7 (требуется дорога 3) 5,6,8 (дорога требуется 2)
Стоимость создания библиотеки в каждом компоненте (2*3=6) + стоимость строительства требуемой дороги (5*2=10) = 16
Стоимость создания библиотеки в каждом узле (7*3=21) = 21
Итак, 16 - это ответ.
Мой код:
Примечание: 1 индексация графика, используемого в этой программе.
#include<bits/stdc++.h>
using namespace std;
class Graph{
int v; // number of vertices
vector<int>*adj;
public:
Graph(int V){
this->v=V+1;
this->adj=new vector<int>[this->v];
}
void addEdge(int u,int v,bool biDir=true){
adj[u].push_back(v);
if(biDir)
adj[v].push_back(u);
}
void bfs(int ar[]){
// create a array of boolean to keep track of visited nodes.
int numComponent=0,numEdge=0;
bool visited[this->v];
for(int i=1;i<this->v;i++)
visited[i]=false;
// for each node in graph
for(int i=1;i<this->v;i++){
if(!visited[i]){
numComponent++;
numEdge+=bfsUtill(i,visited);
}
}
ar[0]=numComponent;
ar[1]=numEdge;
}
int bfsUtill(int src, bool visited[]){
// make a queue and insert src into it
int numEdge=0;
queue<int>q;
q.push(src); // insert src into queue
// mark first node as visited
visited[src]=true;
while(!q.empty()){
int node=q.front();
// visit
cout<<node<<" ";
// remove this node from queue
q.pop();
// visit every node adjacent to node 'node'
// if that node not visited then visit and enque it.
for(int adjNode:adj[node]){
if(!visited[adjNode]){
numEdge++;
visited[adjNode]=true;
q.push(adjNode);
}
}
}
return numEdge;
}
};
// Complete the roadsAndLibraries function below.
long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
// if c_road is greater than c_lib then
if (c_road>c_lib){
return n*c_lib;
}
Graph g(n);
// make graph of given vertices
for(auto x:cities)
g.addEdge(x[0],x[1]);
// Array to store number of component and number of edges need to be repaired
int ar[2];
g.bfs(ar);
long long int libInEach=n*c_lib;
long long int roadAlso= ar[0]*c_lib+(ar[1]*c_road);
return min(libInEach,roadAlso);
}
// driver code
int main(){
int t,n,m,c_lib,c_road;
vector<vector<int>>cities;
vector<int>temp;
cin>>t;
while(t--){
cin>>n,m,c_lib,c_road;
int a,b;
for(int i=0;i<m;i++){
cin>>a>>b;
temp.push_back(a,b);
cities.push_back(temp);
temp.erase();
}
cout<<roadsAndLibraries(n,c_lib,c_road,cities);
}
return 0;
}
Я получаю правильный ответ для некоторых тестовых случаев и неправильный для некоторых тестовых случаев.
Я разместил только требуемый код, вставленный из всей программы. Ввод передается в эту функцию roadsAndLibraries().
Я проверяю вспомогательные функции, и они работают нормально.
- bfs()
- bfsUtill()
Контрольные примеры:
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
Выходные данные для этого теста:
4
12