E – Nearest Black Vertex (atcoder.jp)
Title
If it is not possible to paint each vertex as black or white to satisfy the condition, print No. Otherwise, print Yes
if vertex i is painted black and 00 if white. if white.
Whether the first line has a solution, YES NO
The second line string 1 is black and 0 is white.
A connected undirected graph does not contain self-loops and polygons
The i-th edge links ui and vi,
At least one vertex is drawn black.
The minimum distance between pi and the black point is di
The distance between u and v is the minimum number of edges on the path between u and v
Undirected graph does not contain self-loops and polygons
At least one vertex is drawn black.
The minimum distance between pi and the black point is di
edge weight is 1
The black point is a special point, first assume that a point is a special point, and then run down the shortest path to see if all d conditions are met.
But this does not necessarily determine a special point, and d may require the existence of multiple special points at the same time to be satisfied.
There is no solution to the situation.
In the case of no solution, when there is only one point, if d! = 0 no solution
Two dots if d! = 1 or 0, no solution
3 points, d must be >=0 <= 2,
So d must be >= 0, <= n-1;
Problem Solution Ideas:
Use bfs to search for points, < d is marked as white
Search again, if there is no >= d, then NO, use the bool array to record the situation, and finally output while traversing, you can use the so-called “string” to represent the information of the point.
Question asked whether the pieces meet the requirements:
The first is the situation where black and white pieces need to be obtained.
White chess and black chess are two opposite sides, you can choose one to operate at will.
Here choose white to accept the operation.
It is difficult to know which one can be played as black. At this time, you can think in reverse,
Which one cannot be black? What restrictions does the title impose on black?
Given k pieces, the distance between the black pieces closest to these pieces is required to be di, so
Those whose distance from these chess pieces is less than di cannot be used as white chess pieces, all of them are marked as black chess pieces, and the rest are marked as white chess pieces, so that the black and white situation is obtained.
Then, the title is the distance of the black piece closest to the white piece=di, and then the shortest distance between each piece and the black piece is processed.
Corresponding to the routine of finding the shortest distance from one kind of point to another kind of point, just check whether the distance = di. Does not meet the output no and then return
Output yes after all processing
Code and Analysis
jls code
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
long long abbreviation
int main() {<!-- -->
int N, M;
cin >> N >> M;
***
vector<vector<int>> adj(N);
I thought it was a function, but it was actually an array name
for (int i = 0; i < M; i ++ ) {<!-- -->
int u, v;
cin >> u >> v;
u--, v--;
The vector subscript starts from 0, and uv starts from 1, so u--, v--
adj[u].push_back(v);
adj[v].push_back(u);
The weights are all 1, so there is no need to store them, so the second dimension is directly pb, and iteration can be used when traversing, instead of traversing the entire N,
}
***
vector<bool> black(N, true);
A vector with a size of N and an initial value of true
int K;
cin >> K;
vector<int> p(K), d(K);
p,d vector of size k
for (int i = 0; i < K; i ++ ) {<!-- -->
cin >> p[i] >> d[i];
p[i]--;
Unified subscript
Run dfs k times, start with i, and use bfs to know the distance from each point to i. Use the distance to compare with d[i], and you can set all points that do not meet the requirements to white. But if it is to find the distance, why not use the shortest path?
bfs, while processing, you can judge the point.
shortest path:
After running the shortest path, it is not impossible to traverse other points and judge whether the distance is <d[i].
I don't know much about the premise of bfs, so I need to do this topic. As far as this question is concerned, because you need to know the distance from all points to the current point, it is very suitable for bfs.
***
vector<int> dis(N, -1);
The size is N, the initial value is -1
queue<int> q;
dis[p[i]] = 0;
q.push(p[i]);
\t
while (!q.empty()) {<!-- -->
int x = q. front();
q. pop();
if (dis[x] < d[i]) {<!-- -->
black[x] = false;
}
for (auto y : adj[x]) {<!-- -->
if (dis[y] == -1) {<!-- -->
dis[y] = dis[x] + 1;
q. push(y);
}
}
}
}
***
I don’t understand why I use bfs to search, I need to do some kuangbin search questions
It seems that it is because of the distance from small to large to search outward layer by layer.
bfs is used to handle the distance of each path,
queue<int> q;
vector<int> dis(N, -1);
Can be initialized by the way.
for (int i = 0; i < N; i ++ ) {<!-- -->
if (black[i]) {<!-- -->
q. push(i);
dis[i] = 0;
}
}
Push possible points in.
while (!q.empty()) {<!-- -->
int x = q. front();
q. pop();
for (auto y : adj[x]) {<!-- -->
if (dis[y] == -1) {<!-- -->
dis[y] = dis[x] + 1;
q. push(y);
}
}
}
Process the shortest distance of each black point
***
for (int i = 0; i < K; i ++ ) {<!-- -->
if (dis[p[i]] != d[i]) {<!-- -->
cout << "No\
";
return 0;
}
}
There is no point with the shortest distance d[i]
cout << "Yes\
";
for (int i = 0; i < N; i ++ ) {<!-- -->
cout << black[i];
}
cout << "\
";
return 0;
}
Imitation code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int main(){<!-- -->
int N,M;
cin >> N >> M ;
vector<vector<int> > adj(N);
for(int i = 0;i < M;i ++ ){<!-- -->
int u,v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<bool> black(N,1);
int k;
cin >> k;
vector<int> p(k),d(k);
for(int i = 0;i < k;i ++ ){<!-- -->
cin >> p[i] >> d[i];
p[i] --;
queue<int> q;
vector<int> dis(N,-1);
q.push(p[i]);
dis[p[i]] = 0;
while(q. size()){<!-- -->
int x = q. front();
q. pop();
if(dis[x] < d[i]){<!-- -->
black[x] = false;
}
for(auto y : adj[x]){<!-- -->
if(dis[y] == -1){<!-- -->
dis[y] = dis[x] + 1;
q. push(y);
}
}
}
}
queue<int> q;
vector<int> dis(N,-1);
for(int i = 0;i < N;i ++ ){<!-- -->
if(black[i]){<!-- -->
q. push(i);
dis[i] = 0;
}
}
while(q. size()){<!-- -->
int x = q. front();
q. pop();
for(auto y : adj[x]){<!-- -->
if(dis[y] == -1){<!-- -->
dis[y] = dis[x] + 1;
q. push(y);
}
}
}
for(int i = 0;i < k;i ++ ){<!-- -->
if(dis[p[i]] != d[i]){<!-- -->
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
for(int i = 0;i < N;i ++ ){<!-- -->
cout << black[i] ;
}
cout << "\
" ;
return 0;
}
Routine:
1) bfs without border weight (weight is 1) the shortest path
Prerequisites: find the shortest path, no edge weight graph.
Scenario:
1) Catch That Cow
- Walking: FJ can move from any point X to the points X – 1 or X + 1 in a single minute
- Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
- Each time you move, the time increases by one. Time can also be regarded as a kind of distance.
2) nearest Black Vertex
- At least one vertex is painted black.
- For every i=1,2,…,K, the following holds:
- the minimum distance between vertex pi? and a vertex painted black is exactly di?.
- Mark the pieces that do not meet the requirements as white, and then find the distance of each white piece to the nearest black piece.
It is necessary to find the shortest distance between graph points with an edge weight of 1.
Response:
1. Find the shortest path from one point to n points:
Use this point as a starting point.
2. Find the shortest distance from one type of point to another type of point
Push all one of the points into the loop, and then set dis to 0.n starting points.
About why not use spfa, dijkstra
Tip:
When many students see the “shortest path”, they think of “Dijkstra’s algorithm” reflexively. Why can BFS traversal also find the shortest path?
This is because Dijkstra’s algorithm solves the weighted shortest path problem, but what we focus on here is the unweighted shortest path problem. It can also be regarded as the weight of each edge is 1. Such a shortest path problem can be solved with BFS.
In an interview, you might prefer to write BFS instead of Dijkstra. After all, there are not many people who can guarantee that they can write Dijkstra’s algorithm correctly.
Summary:
BFS is the optimal solution to deal with the shortest path of unweighted edges.
spfa, dijkstra is used to deal with the right edge
Shortest path with edge weight –> dijkstra, spfa
Unweighted shortest path –> bfs
#bfs shortest path without border weight