问题：

竞争编码问题。无向图的BFS。获得WA

孙夕

2023-03-14

我正在Hackerrank上实现图形算法。
问题陈述：
HackerLand的统治者认为该国的每个公民都应该可以访问图书馆。不幸的是，HackerLand被龙卷风袭击，摧毁了所有图书馆并阻碍了道路！由于您是HackerLand最伟大的程序员，统治者希望您帮助修复道路并有效地建造一些新图书馆。
HackerLand有n个城市，编号从1到n。这些城市由m条双向道路连接。如果：

他们的城市有一个图书馆。
他们可以通过公路从他们的城市到一个有图书馆的城市。

下图是HackerLand的示例地图，其中虚线表示受阻的道路：

我的方法是：我用给定的城市和道路绘制一个图，其中每个城市表示图中的一个节点，每条道路表示一条边。我使用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;
}

我得到了一些测试用例的正确答案和一些测试用例的不正确答案。
我只发布了所需的代码，嵌入了整个程序。输入被传递到这个函数路和库（）。
我测试助手函数，这些都工作正常。

-bfs（）
-bfsU（）
测试用例：

此测试用例的输出：

4
12

共有1个答案

井修雅

2023-03-14

我编辑了你的代码。这可能适用于您在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;
}

类似资料：

Google App Engine中的竞争问题

问题内容：我在Google App Engine中遇到争用问题，并尝试了解发生了什么。我有一个注释为的请求处理程序： ..并且在该代码中，我获取了一些东西，更新了其他东西，等等。但是有时在请求期间日志中会出现这样的错误： ..之后是堆栈跟踪。如果需要，我可以使用整个堆栈跟踪进行更新，但这有点长。我不明白为什么会这样。查看我的代码行中的异常，我在一个完全不同的实体（Round）上运行。错误消息
SQL Server竞争条件问题

问题内容：（注意：这是针对MS SQL Server的）假设您有一个具有主键标识列和CODE列的表ABC。我们希望此处的每一行都有一个唯一的，顺序生成的代码（基于一些典型的校验位公式）。假设您有另一个仅具有一行的表DEF，该表存储下一个可用的CODE（想象一个简单的自动编号）。我知道像下面这样的逻辑将呈现一种竞争状态，其中两个用户可能最终得到相同的CODE：我知道，两个用户可能会卡在步骤
竞争规划算法Sock图概率问题

先让我把问题贴上。这个问题是基于一个（几乎）真实的故事。一个无名的孩子有一大堆干净的袜子。这一堆包含了m双有图片和图案的袜子和n只纯白的袜子。每双袜子由两只相同的袜子组成，每一双都是独一无二的--没有两双看起来是一样的。所有纯白的袜子都是一样的。每天，孩子们从袜子堆里随机挑选两只，穿上，然后去上学。但今天是照相日，孩子需要穿两只一模一样的袜子。于是孩子随机挑选了两只袜子，如果两只袜子都一样，孩子
竞争性编程中的平均中位数模式问题

我在一次公司入学考试中得到了以下问题。除4个测试用例外，所有测试用例均通过。有没有人能试着找出可能出现的情况，哪些可能会失败。问题和解决方案如下：均值、中位数和模式给定n个整数，求其平均中值和模式。您需要填写一个接受输入整数“input1”（1）的函数平均数和中位数必须正确到小数点后六位。平均值：定义为数组中所有数字的平均值。中位数：定义为数组的中间元素。如果n是偶数，则中值是两个中间
如何解决 Redis 的并发竞争 Key 问题？

本文向大家介绍如何解决 Redis 的并发竞争 Key 问题？相关面试题，主要包含被问及如何解决 Redis 的并发竞争 Key 问题？时的应答技巧和注意事项，需要的朋友参考一下所谓 Redis 的并发竞争 Key 的问题也就是多个系统同时对一个 key 进行操作，但是最后执行的顺序和我们期望的顺序不同，这样也就导致了结果的不同！推荐一种方案：分布式锁（zookeeper 和 redis 都可
竞争条件

9.1. 竞争条件在一个线性(就是说只有一个goroutine的)的程序中，程序的执行顺序只由程序的逻辑来决定。例如，我们有一段语句序列，第一个在第二个之前(废话)，以此类推。在有两个或更多goroutine的程序中，每一个goroutine内的语句也是按照既定的顺序去执行的，但是一般情况下我们没法去知道分别位于两个goroutine的事件x和y的执行顺序，x是在y之前还是之后还是同时发生是没法

竞争编码问题。无向图的BFS。获得WA

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档