SCNU-Algorithms-MS-2023-Greedy Algorithm

Greedy Algorithm

1-1 Travel Planning

Title

With a self-driving travel route map, you will know the length of highways between cities and the tolls charged on the highways. Now you need to write a program to help tourists who come to consult find the shortest path between the departure point and the destination. If there are several paths that are the shortest, then the cheapest path needs to be output.

Input format:
Input instructions: The first line of the input data gives four positive integers N, M, S, and D, where N (2≤N≤500) is the number of cities. By the way, assume that the city number is 0~(N?1 ); M is the number of highways; S is the city number of the departure place; D is the city number of the destination. In the subsequent M lines, each line gives information about a highway, namely: City 1, City 2, highway length, and toll amount. They are separated by spaces. The numbers are all integers and do not exceed 500. The input guarantees the existence of a solution.

Output format:
Output the length of the path and the total charge in one line. Separate the numbers with spaces. There should be no extra spaces at the end of the output.

Input example:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

Example output:

3 40

Floyd’s algorithm is mainly used to find the shortest path between the starting point and the end point. The main steps of Floyd’s algorithm for this problem are as follows:

void Floyd(int N) {<!-- -->
//CODE
for (int i = 0; i < N; i + + ) {<!-- -->
for (int j = 0; j < N; j + + ) {<!-- -->
for (int n = 0; n < N; n + + ) {<!-- -->
if (Path_long[i][j] > Path_long[i][n] + Path_long[n][j]) {<!-- -->
Path_long[i][j] = Path_long[i][n] + Path_long[n][j];
Path_long[j][i] = Path_long[i][n] + Path_long[n][j];
Cost[i][j] = Cost[i][n] + Cost[n][j];
Cost[j][i] = Cost[i][n] + Cost[n][j];
}
else if(Path_long[i][j] == Path_long[i][n] + Path_long[n][j]) {<!-- -->
Cost[i][j] = min(Cost[i][j], Cost[i][n] + Cost[n][j]);
Cost[j][i] = min(Cost[i][j], Cost[i][n] + Cost[n][j]);
}
}
}
}
}

Mainly three levels of nested loops, the first two levels of loops mainly traverse all Path_long nodes. Among them, Path_long[ i ][ j ] represents the distance from city i to city j (999 if there is no way). For each Path_long[ i ][ j ], find any city n. If you go from i to n and then to The route from j is shorter than the direct route from i to j, so the node needs to be updated, and the update value is the current smaller route, that is, the route from i to n and then to j.

Path_long[i][j] = Path_long[i][n] + Path_long[n][j];
Path_long[j][i] = Path_long[i][n] + Path_long[n][j];

At the same time, if the path from i to j and from i to n and then to j are the same, then choose based on the cost, who has the smaller cost, which way to choose.

else if(Path_long[i][j] == Path_long[i][n] + Path_long[n][j]) {<!-- -->
Cost[i][j] = min(Cost[i][j], Cost[i][n] + Cost[n][j]);
Cost[j][i] = min(Cost[i][j], Cost[i][n] + Cost[n][j]);
}

Therefore, the complete code is as follows:

#include

int Path[501][501];
int Path_long[501][501];
int Cost[501][501];

int min(int v1, int v2) {
if (v1 > v2)
return v2;
else
return v1;
}


void Floyd(int N) {<!-- -->
//CODE
for (int i = 0; i < N; i + + ) {<!-- -->
for (int j = 0; j < N; j + + ) {<!-- -->
for (int n = 0; n < N; n + + ) {<!-- -->
if (Path_long[i][j] > Path_long[i][n] + Path_long[n][j]) {<!-- -->
Path_long[i][j] = Path_long[i][n] + Path_long[n][j];
Path_long[j][i] = Path_long[i][n] + Path_long[n][j];
Cost[i][j] = Cost[i][n] + Cost[n][j];
Cost[j][i] = Cost[i][n] + Cost[n][j];
}
else if(Path_long[i][j] == Path_long[i][n] + Path_long[n][j]) {<!-- -->
Cost[i][j] = min(Cost[i][j], Cost[i][n] + Cost[n][j]);
Cost[j][i] = min(Cost[i][j], Cost[i][n] + Cost[n][j]);
}
}
}
}
}

int main() {

int N, M, S, D;
std::cin >> N >> M >> S >> D;
for (int i = 0; i < N; i + + ) {
for (int j = 0; j < N; j + + ) {
Path_long[i][j] = 999;
Cost[i][j] = 999;
}
}
for (int i = 0; i < M; i + + ) {
int city1, city2, path_long, cost;
std::cin >> city1 >> city2 >> path_long >> cost;
Path_long[city1][city2] = path_long;
Path_long[city2][city1] = path_long;
Cost[city1][city2] = cost;
Cost[city2][city1] = cost;
}

Floyd(N);
std::cout << Path_long[S][D] << " " << Cost[S][D];
}

1-2 Rescue 007 (upgraded version)

Title

There is a plot in the old movie "Live and Let Die" where 007 was captured by a drug dealer on a small island in the center of a crocodile pool. He used an extremely bold method to escape - stepping directly into the pool. A series of crocodile's big heads jumped onto the shore! (It is said that the stuntman was bitten on the foot by the last crocodile. Fortunately, he was wearing specially thickened boots and escaped.)

Assume that the crocodile pool is a square with a length and width of 100 meters, the center coordinate is (0, 0), and the northeast corner coordinate is (50, 50). Chixin Island is a circle with (0, 0) as the center and a diameter of 15 meters. Given the coordinates of the crocodiles distributed in the pool and the maximum distance that 007 can jump at one time, you need to point him to the shortest escape path - the so-called "shortest" means that 007 has the least number of steps to jump.

Input format:

First, the first line gives two positive integers: the number of crocodiles N (≤100) and the maximum distance D that 007 can jump in one time. N lines follow, each giving the (x,y) coordinates of an alligator. Note: No two crocodiles will stay at the same spot.
Output format:
If it is possible for 007 to escape, first output the minimum number of steps that 007 needs to jump on the first line, and then starting from the second line, each line gives the coordinates (x, y). If escape is not possible, output 0 as the number of jump steps on the first line. If the shortest path is not unique, output the solution with the closest first hop. The question ensures that such a solution is unique.

Input example 1:

17 15
10-21
10 21
-40 10
30-50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

Output sample 1

4
0 11
10 21
10 35
1

Input example 2:

4 13
-12 12
12 12
-12 -12
12 -12

Output sample 2

0

Data structure: Each node contains: crocodile coordinates and distance to the origin.

class Node {<!-- -->
public:
int x, y; //Crocodile coordinates
double first_step; // distance to far point
bool operator<(const Node & amp; t) const {<!-- -->
return (this->first_step < t.first_step);
}
};
Node node[N];

const int INF = 99999;
const int N = 101;
int dist[N];
int path[N]; // When reaching i, j is the prefix of i, path[i] = j;
int n, d; //n represents the number of crocodiles, d is the distance

INF is set to the maximum value, the place that has not been reached; N is the maximum number of crocodiles;
The idea of this question: Use BFS breadth to find a route to the end point. Before BFS, it is necessary to traverse the positions of all crocodiles once, sort each crocodile according to the distance from the origin, and push the crocodiles that can be reached in the first step into the queue for the elements of the initial BFS queue.

for (int i = 0; i < n; i + + ) {<!-- -->
int x, y;
std::cin >> node[i].x >> node[i].y;
node[i].first_step = std::sqrt(node[i].x * node[i].x + node[i].y * node[i].y);
}
std::sort(node, node + n);
\t
for (int i = 0; i < n; i + + ) {<!-- -->
if (node[i].first_step > 7.5 & amp; & amp; node[i].first_step < d + 7.5) {<!-- -->
q.push(i);
dist[i] = 1;
}
}

Then the normal BFS idea is to take the value of the first element and then pop the first element of the queue, then search for the node attached to the element, and push it into the queue if it meets the push requirement. But it should be noted that after taking out the first element, you need to judge whether the end point can be reached in the next step. For the four quadrants, different methods are used to calculate which edge is closer. If you can't reach the end in one step, continue the cycle. The code for the judgment method is as follows (temp_index is the subscript to retrieve the first element):

if (node[temp_index].x >= 0 & amp; & amp; node[temp_index].y >= 0)
distance_end = min_2(50 - node[temp_index].x, 50 - node[temp_index].y);
else if (node[temp_index].x >= 0 & amp; & amp; node[temp_index].y <= 0)
distance_end = min_2((50 - node[temp_index].x), (node[temp_index].y + 50));
else if (node[temp_index].x <= 0 & amp; & amp; node[temp_index].y >= 0)
distance_end = min_2(node[temp_index].x + 50, 50 - node[temp_index].y);
else if (node[temp_index].x <= 0 & amp; & amp; node[temp_index].y <= 0)
distance_end = min_2(node[temp_index].x + 50, node[temp_index].y + 50);
if (distance_end <= d) {<!-- --> // If the next step can reach the end point
if (dist[n] == INF) {<!-- -->
dist[n] = dist[temp_index] + 1;
path[n] = temp_index; //Update the prefix of the final node
break;
}
}

If you cannot reach it in the next step, you need to search all unvisited nodes and only find nodes that can be jumped to in one step. This is also the reason for choosing BFS. Only the surrounding nodes are searched and inserted into the queue. In the initialization, the maximum value will be assigned to the dist array. If the node value is equal to the maximum value, it will be regarded as not being visited. Then the distance from the point to the first element will be calculated, and if appropriate, it will be inserted into the queue. It is worth noting that the shortest path for this question is the shortest number of jumps, not the distance traveled. Therefore, the idea of this question is feasible, and you only need to slowly approach the end point step by step. For the matching nodes, add one operation to the corresponding dist array, which is recorded as the jump number, and the path array remembers the prefix.

for (int i = 0; i < n; i + + ) {<!-- -->
if (dist[i] == INF) {<!-- --> //If it has not been stepped on
double distance = std::sqrt((node[i].x - node[temp_index].x) * (node[i].x - node[temp_index].x) + (node[i].y - node[ temp_index].y) * (node[i].y - node[temp_index].y));
if (distance <= d) {<!-- --> // Distance is enough to jump
q.push(i);
dist[i] = dist[temp_index] + 1;
path[i] = temp_index;
}
}
}

Then let's go back to the situation of reaching the end point, because this method loops again and again. Basically, the jump number will be increased by one after each loop. If there is a node that reaches the end first, dist[n] will be assigned a value, and the assigned value will be certain. It is the path reached by the fastest number of cycles. As for whether it is a detour or whether it is the shortest distance, this question does not care. At the same time, according to path[n]=temp_index, we can go back to the initial node again and again to output the answer.

if (distance_end <= d) {<!-- --> // If the next step can reach the end point
if (dist[n] == INF) {<!-- -->
dist[n] = dist[temp_index] + 1;
path[n] = temp_index; //Update the prefix of the final node
break;
}

When outputting the result, you only need to backtrace, push the node into the stack, and then use the loop to output.

void Output( std::stack<int> & amp; s) {<!-- -->
if (!s.empty()) {<!-- -->
int index = s.top();
s.pop();
std::cout << node[index].x << " " << node[index].y << std::endl;
Output(s);
}
}

int end_flag = path[n];

while (end_flag != -1) {<!-- -->
s.push(end_flag);
end_flag = path[end_flag];
}
Output(s);

The complete code is as follows:

#include
#include
#include
#include 
#include

const int INF = 99999;
const int N = 101;
int dist[N];
int path[N]; // When reaching i, j is the prefix of i, path[i] = j;
int n, d; //n represents the number of crocodiles, d is the distance

class Node {
public:
int x, y; //Crocodile coordinates
double first_step; // distance to far point
bool operator<(const Node & amp; t) const {
return (this->first_step < t.first_step);
}
};

Node node[N];

void Init_2() {
for (int i = 0; i < N; i + + ) {
dist[i] = INF;
path[i] = -1;
}
}

int min_2(int v1, int v2) {
if (v1 >= v2)
return v2;
else
return v1;
}

void BFS() {
std::queue q; //Use BFS to find the shortest path
double distance_end;
//Add the crocodile that can be stepped on in the first step to the queue
for (int i = 0; i < n; i + + ) {
if (node[i].first_step > 7.5 & amp; & amp; node[i].first_step < d + 7.5) {
q.push(i);
dist[i] = 1;
//path[i] = -1;
}
}

while (!q.empty()) {
int temp_index = q.front();
q.pop();
if (node[temp_index].x >= 0 & amp; & amp; node[temp_index].y >= 0)
distance_end = min_2(50 - node[temp_index].x, 50 - node[temp_index].y);
else if (node[temp_index].x >= 0 & amp; & amp; node[temp_index].y <= 0)
distance_end = min_2((50 - node[temp_index].x), (node[temp_index].y + 50));
else if (node[temp_index].x <= 0 & amp; & amp; node[temp_index].y >= 0)
distance_end = min_2(node[temp_index].x + 50, 50 - node[temp_index].y);
else if (node[temp_index].x <= 0 & amp; & amp; node[temp_index].y <= 0)
distance_end = min_2(node[temp_index].x + 50, node[temp_index].y + 50);

if (distance_end <= d) {<!-- --> // If the next step can reach the end point
if (dist[n] == INF) {<!-- -->
dist[n] = dist[temp_index] + 1;
path[n] = temp_index; //Update the prefix of the final node
break;
}
}

for (int i = 0; i < n; i + + ) {<!-- -->
if (dist[i] == INF) {<!-- --> //If it has not been stepped on
double distance = std::sqrt((node[i].x - node[temp_index].x) * (node[i].x - node[temp_index].x) + (node[i].y - node[ temp_index].y) * (node[i].y - node[temp_index].y));
if (distance <= d) {<!-- --> // Distance is enough to jump
q.push(i);
dist[i] = dist[temp_index] + 1;
path[i] = temp_index;
}
}
}
}
}

void Output( std::stack & amp; s) {
if (!s.empty()) {
int index = s.top();
s.pop();
std::cout << node[index].x << " " << node[index].y << std::endl;
Output(s);
}
}


int main() {
Init_2();
std::cin >> n >> d;
std::stack s;

//Diameter 15, radius 7.5, if d>42.5, you can skip it in one step
if (d >= 42.5) {
std::cout << 1 << std::endl;
return 0;
}

for (int i = 0; i < n; i + + ) {
int x, y;
std::cin >> node[i].x >> node[i].y;
node[i].first_step = std::sqrt(node[i].x * node[i].x + node[i].y * node[i].y);
}
std::sort(node, node + n);
BFS();
if (dist[n] == INF) {//Failed to land successfully
std::cout << "0" << std::endl;
return 0;
}
//Output program
std::cout << dist[n] << std::endl;
int end_flag = path[n];
while (end_flag != -1) {
s.push(end_flag);
end_flag = path[end_flag];
}
Output(s);
}

1-3 Uniqueness of Minimum Spanning Tree

Title

Given a weighted undirected graph, if it is a connected graph, there is at least one minimum spanning tree, and sometimes the minimum spanning tree is not unique. This question requires you to calculate the total weight of the minimum spanning tree and determine whether it is unique.

Input format:

First, the first line gives two integers: the number of vertices N (≤500) and the number of edges M in the undirected graph. Then M lines, each line gives the two endpoints and weight of an edge, in the format of "vertex 1 vertex 2 weight", where the vertices are numbered from 1 to N, and the weight is a positive integer. The question ensures that the total weight of the minimum spanning tree will not exceed 2^30.

Output format:

If there is a minimum spanning tree, first output its total weight in the first line, and output "Yes" in the second line if this tree is unique, otherwise output "No". If the tree does not exist, first output "No MST" in the first line, and output the number of connected sets of the graph in the second line.

Input example 1:

5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5

Input example 1:

11
Yes

Input example 2:

4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

Output sample 2:

4
No

Input example 3:

5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

Output sample 3:

No MST
2

The data structure of this question is as follows:

struct Edge
{<!-- -->
int u, v, w;
};
int N, M, f[501];
int Graph[501][501];
Edge edge[250000];
bool vis[501];

In Edge, u represents the starting node, v represents the reaching node, and w represents the weight of this edge. At the same time, when the input data is initialized, the edge that can be reached by the Graph will be given a weight value of w.

Among them, there are two core functional steps of the algorithm: the find() function can find the root node of the node, and the merge() function connects the added new edges to facilitate the find() function to find its root node. Specifically The steps are explained below.

int find(int x) {<!-- -->
if (x == f[x]) {<!-- -->
return x;
}
return f[x] = find(f[x]);
}

void merge(int a, int b) {<!-- -->
int u = find(a);
int v = find(b);
f[v] = u;
}

If you need to find the minimum spanning tree, you need to use Kruskal's algorithm (kruskal) to sort the weights of all edges and gradually add the edges with the smallest weight. At the same time, the edges cannot form a cycle.

std::sort(edge, edge + M, cmp);

Loop according to the number of edges. When the inserted edges reach N-1, the loop ends. For each edge, you need to see whether this edge can be inserted and whether it will form a ring. How to judge whether a ring will be formed? Let's first look at how the first two or three edges are inserted.

sum + = edge[i].w;
merge(u, v);
cnt + + ;
if (cnt == N - 1) {<!-- -->
break;

void merge(int a, int b) {<!-- -->
int u = find(a);
int v = find(b);
f[v] = u;
}

After adding an edge, sum represents the total weight value, and the corresponding value needs to be added. At the same time, the merge function is executed. Now let's take a look at how the merge function is executed. If the added edge is 1 2 1, then u is 1 and v is 2, then f[2] = 1. Therefore, element 2 in the f[] array stores the root node element. What about inserting 2 3 1 again? u = find(2) = 1, therefore f[3] = 1.
We can know that all the nodes added point to the root node. When adding 3 1 1, we will find find(3) == find(1), so a loop will be formed and cannot be added.

So, the minimum spanning tree can be generated normally, how to judge whether it is unique? An example according to my understanding:

1 2 1
2 3 1

Suppose we add these two edges, 1 2 3 has been connected into a line. At this time, the next two edges can be added, and all the nodes are connected at the same time, and the weights are the same.

3 4 2
4 1 2

Therefore, if they are not unique, there must be two weights that can be replaced with each other, and one of them can be used arbitrarily. Then the code idea is as follows:

for (int j = i + 1; j < M & amp; & amp; edge[i].w == edge[j].w; j + + ) {<!-- -->
    int u1 = find(edge[j].u);
    int v1 = find(edge[j].v);
    if (u1 == u & amp; & amp; v1 == v || u1 == v & amp; & amp; v1 == u) {<!-- -->
    flag = false;
    break;
    }

After we add 3 4 2 normally, f[] of 1 2 3 4 all point to the root node 1, then we continue to check several edges with the same weight. If the subsequent edge is for a purpose, then it is directly judged to be not unique. For example: the edge of 3 4 2. Note that we have not performed the merge operation yet. After find, 3 4 can be regarded as the subtree formed by 4 connected to the 1 node. And when we look at the subsequent edges, we find that 4 1 2 has the same weight, and is also a subtree formed by connecting 4 to the 1 node, but in a different order, so u1 == u and u1 == v are both considered. This way we can check whether the subtree is unique.

The complete code is as follows:

#include
#include 

struct Edge
{<!-- -->
int u, v, w;
};
int N, M, f[501];
int Graph[501][501];
Edge edge[250000];
bool vis[501];

void dfs(int x) {
vis[x] = true;
for (int i = 1; i <= N; i + + ) {
if (Graph[x][i] & amp; & amp; !vis[i]) {
dfs(i);
}
}
}

int Count() {
int cnt = 0;
for (int i = 1; i <= N; i + + ) {
if (!vis[i]) {
cnt + + ;
dfs(i);
}
}
return cnt;
}



void Init() {
for (int i = 0; i <= N; i + + ) {
f[i] = i;
}

for (int i = 0; i < M; i + + ) {
int u, v, w;
std::cin >> u >> v >> w;
edge[i].u = u;
edge[i].v = v;
edge[i].w = w;
Graph[u][v] = w;
Graph[v][u] = w;

}

}


int find(int x) {<!-- -->
if (x == f[x]) {<!-- -->
return x;
}
return f[x] = find(f[x]);
}

void merge(int a, int b) {<!-- -->
int u = find(a);
int v = find(b);
f[v] = u;
}

bool cmp(Edge e1, Edge e2) {
return e1.w < e2.w;
}

int main() {
    std::cin >> N >> M;
    Init();
    std::sort(edge, edge + M, cmp);
    bool flag = true;
    int sum = 0; int cnt = 0;
    for (int i = 0; i < M; i + + ) {
    int u = find(edge[i].u);
    int v = find(edge[i].v);
    //Exclude adding an edge to become a ring
    if (u != v) {
    for (int j = i + 1; j < M & amp; & amp; edge[i].w == edge[j].w; j + + ) {<!-- -->
    int u1 = find(edge[j].u);
    int v1 = find(edge[j].v);
    if (u1 == u & amp; & amp; v1 == v || u1 == v & amp; & amp; v1 == u) {<!-- -->
    flag = false;
    break;
    }
    }
    sum + = edge[i].w;
    merge(u, v);
    cnt + + ;
    if (cnt == N - 1) {
    break;
    }
    }
    }
    int num = Count();
    if (num == 1) {
    std::cout << sum << std::endl;
    if (flag) {
    std::cout << "Yes";
    }
    else {
    std::cout << "No";
    }
    }
    else {
    std::cout << "No MST" << std::endl;
    std::cout << num;
    }
}
\t