当前位置:网站首页>Practice of concurrent search
Practice of concurrent search
2022-07-05 23:07:00 【BugMaker-shen】
List of articles
Is it relatives
We use merge The optimization of the , Don't use find It's optimized
#include <iostream>
#include <vector>
using namespace std;
int SIZE = 0;
int* parent = nullptr; // Record the parent node of each node
int* height = nullptr; // Record the floor height of the root node
// return x The number of the root node of the tree
int find_root(int x) {
if (x <= 0 || x >= SIZE) {
return -1;
}
while (x != parent[x]) {
x = parent[x];
}
return x;
}
// Merge x and y Where the collection is
void merge(int x, int y) {
x = find_root(x);
y = find_root(y);
if (x != y) {
// here x and y Are root nodes , Who is short, who is the child node
if (height[x] > height[y]) {
parent[y] = x;
}
else {
if (height[x] == height[y]) {
// y As the root of the merged tree , The height of the root node should be +1
height[y]++;
}
parent[x] = y;
}
}
}
int main() {
int m = 0;
int p = 0;
int n = 0;
cin >> n >> m >> p;
SIZE = n + 1;
parent = new int[SIZE];
height = new int[SIZE];
for (int i = 0; i < SIZE; i++) {
height[i] = 1;
parent[i] = i; // In limine , The parent node of each node is itself
}
int p1, p2; // Two people
for (int i = 0; i < m; i++) {
cin >> p1 >> p2;
merge(p1, p2);
}
vector<pair<int, int>> query;
for (int i = 0; i < p; i++) {
cin >> p1 >> p2;
query.push_back(pair<int, int>(p1, p2));
}
for (auto q : query) {
cout << (find_root(q.first) == find_root(q.second) ? "YES" : "NO") << endl;
}
delete[] parent;
delete[] height;
parent = nullptr;
height = nullptr;
return 0;
}
/* 6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 */
The best way to avoid congestion
3 3 1 3 # 3 Districts 、3 side 、 from 1 District to 3 District
1 2 2 # from 1 District to 2 The congestion degree of the district is 2
2 3 1
1 3 3
The title says to plan a path , Make the maximum value of the degree of congestion passing through the road minimum . The test case output 2, It means we started from 1 District to 3 District , You can go 1->2->3, At this time, the maximum congestion is 2; You can also go 1->3, At this time, the maximum congestion is 3; Therefore, the test case output 2
We use kruskal Algorithm , Start with the edge with less congestion , Until connected s Area and t District , In this way, the last selected edge must be the one with the greatest congestion of the selected road , The least congested road is not selected , In this way, the maximum value selected on the basis of connectivity can be minimized
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int* parent = nullptr;
struct Edge {
Edge(int start, int end, int w)
: start_(start)
, end_(end)
, w_(w)
{
}
int start_;
int end_;
int w_;
};
// Find No x The root node of the node
int find(int x) {
if (x == parent[x]) {
return x;
}
else {
// find Optimize , In the process of finding the root node , Change the parent node of the traversed node to the root node
parent[x] = find(parent[x]);
return parent[x];
}
}
int main(){
int n, num_edge, s, t;
cin >> n >> num_edge >> s >> t;
parent = new int[n + 1](); // n Districts , To make the number correspond to the subscript , Open up one more
vector<Edge> edges;
int start, end, w;
for (int i = 0; i < num_edge; i++) {
cin >> start >> end >> w;
edges.emplace_back(start, end, w);
// initialization parent Array
parent[start] = start;
parent[end] = end;
}
// The edges are arranged in ascending order
sort(edges.begin(), edges.end(),
[](const Edge& e1, const Edge& e2) ->bool{
return e1.w_ < e2.w_;
});
for (int i = 0; i < num_edge; i++) {
int root1 = find(edges[i].start_);
int root2 = find(edges[i].end_);
if (root1 != root2) {
// The root node is different , Can be connected
parent[root1] = root2;
if (find(s) == find(t)) {
// A new edge is selected , Will judge whether it is connected s Area and t District ; No new edges are selected in this cycle , Then there is no need to judge whether it is connected s Area and t District
cout << edges[i].w_ << endl;
}
}
}
delete[] parent;
return 0;
}
/* 3 3 1 3 1 2 2 2 3 1 1 3 3 */
边栏推荐
- 从 1.5 开始搭建一个微服务框架——日志追踪 traceId
- Common JVM tools and optimization strategies
- Three. JS VR house viewing
- 【Note17】PECI(Platform Environment Control Interface)
- Three.JS VR看房
- Error when LabVIEW opens Ni instance finder
- Global and Chinese markets for welding products 2022-2028: Research Report on technology, participants, trends, market size and share
- VOT Toolkit环境配置与使用
- Composition of interface
- Déterminer si un arbre binaire est un arbre binaire complet
猜你喜欢
Paddy serving v0.9.0 heavy release multi machine multi card distributed reasoning framework
Google Maps case
3:第一章:认识JVM规范2:JVM规范,简介;
Activate function and its gradient
Arduino measures AC current
并查集实践
Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
[speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
SPSS analysis of employment problems of college graduates
d3dx9_ How to repair 31.dll_ d3dx9_ 31. Solution to missing DLL
随机推荐
2022 R2 mobile pressure vessel filling review simulation examination and R2 mobile pressure vessel filling examination questions
两数之和、三数之和(排序+双指针)
Getting started stm32--gpio (running lantern) (nanny level)
Sum of two numbers, sum of three numbers (sort + double pointer)
2022 G3 boiler water treatment simulation examination and G3 boiler water treatment simulation examination question bank
audiopolicy
[speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
C Primer Plus Chapter 9 question 10 binary conversion
Nangou Gili hard Kai font TTF Download with installation tutorial
Selenium+pytest automated test framework practice
一文搞定JVM常见工具和优化策略
2.13 summary
Hainan Nuanshen tea recruits warmhearted people: recruitment of the product experience recommender of Nuanshen multi bubble honey orchid single cluster
Alibaba Tianchi SQL training camp task4 learning notes
One article deals with the microstructure and instructions of class
Media query: importing resources
audiopolicy
Paddy serving v0.9.0 heavy release multi machine multi card distributed reasoning framework
Finally understand what dynamic planning is
终于搞懂什么是动态规划的