竞争编码问题。无向图的BFS。正在获取WA

Question

我正在Hackerrank上实现图形算法。Problem statement：HackerLand的统治者认为，该国的每个公民都应该可以使用图书馆。不幸的是，HackerLand遭受龙卷风袭击，龙卷风摧毁了其所有图书馆并阻碍了道路！由于您是HackerLand上最伟大的程序员，因此统治者希望您的帮助来修复道路并有效地构建一些新库。HackerLand有n个城市，编号从1到n。城市之间通过m条双向道路相连。在以下情况下，公民可以使用图书馆：

1. 他们的城市有图书馆。
2. 他们可以从城市到有图书馆的城市乘公路旅行。

下图是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算法来查找图形的连接组件。然后在每个组件中建立一个库，并构建最少数量的道路，以使组件保持连接状态。

答案：至少撤消两个。

1. 在每个组成部分中建立图书馆的成本+修路以使每个组成部分的道路数量最少。
2. [在每个城市建立图书馆。在上述情况下，修路成本为2美元(c_road=2)，而图书馆建设成本为3 (c_lib=3)。在这里，此图包含两个组件：
3. 1,2,3,7（所需道路为3）
4. 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

Answer 1

我编辑了您的代码。这可能适用于您在hackerrank上的测试用例。在给定的测试用例上，这很好。在任何组件中，如果总顶点数为n，则可以表示相同连接的组件的最小边数为n-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=1;
            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-1;
        }
};

// 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;
}