IOI 2000 - Walls
Algorithm used: BFS
Time Complexity: O(NM²)
In this problem, M fields are described where each field is surround by some walls. A town is situated at the junction of two or more walls. A member from certain towns need at a common field, by crossing as few walls as possible. Members are not allowed to enter towns. Find the minimum number of walls that need to be crossed by the members, followed with the field number where all the members will meet.
In the example below, there are 6 towns, and members in towns 1 and 6 need to find a meeting field.
The two members can meet in field 1, with the member from 6 crossing one wall
They could also meet in field 2, with the member from 1 crossing one wall
This problem can be represented as a graph problem where the fields and walls are the nodes, and edges are drawn between fields and walls, depending on the input. Notice that all fields will only be adjacent to walls, and all walls will only be adjacent to fields. While reading in the input, make an adjacency list for each wall (edge), where each wall will be recorded as (town a, town b). This means that there is a wall between town a and town b. Similarly, make an adjacency list for each field, where each field is adjacent to walls surrounding it. This is because based on the way the input is given, we cannot directly find out if two fields are adjacent to each other, but we can find out if a field is adjacent to a certain wall or not and vice versa.
To find out if a field will yield the minimum crossing sum, treat every field as a meeting place and count the number of walls the members will have to pass to reach field i. To find the minimum number of walls, a shortest path algorithm can be used to find the answer. Run a BFS from every field to check if the current field could be a meeting place. Use the field adjacency to go from field to wall and use the wall adjacency list to go from wall to field. Every time we go from field to wall, we need to update the number of fields crossed in order to get to the current wall, not including the last field traversed. So, from field to wall, the number of fields the current wall has seen is the same as the number of fields the previous field has traversed. But, when we go from a wall to a field, the number of fields the current field has traversed will be the number of fields traversed by the previous wall + 1. At every pass of the BFS we update the number of fields traversed and not the number of walls traversed because our BFS starts with a field. So, when the BFS moves from field to field, it actually means that a road as been crossed. This is also why we only increment number of fields traversed by one when we move from wall to field.
After the BFS ends, we need to find out the minimum number of fields crossed by each town to get to the starting field. To do this, maintain an array which will store the smallest number of fields crossed by every field. Loop over wall (you can do this by iterating over every element in the fields adjacency list). The walls will be recorded as (town a, town b). Break this apart and check if town a has a member and if town b has a member. If so, then the number of walls traversed by a and b via the current field (the one whose adjacency list is being traversed) will be equal to the number of walls traversed by the current field because 0 walls traversed to get from current field to town a and town b + number of field traversed by current field. Reduce the counts for the towns if needed with the number of fields traversed for the current field.
Finally, loop over the array mentioned previously, and add the minimum number of fields traversed to the answer, if town is a member. If the sum is less than any minimum crossing sum encountered so far, change the minimum crossing sum such that is is now the current sum computed, and record the field number for which the BFS was done.
Code
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 251;
vector <vector <pair <int, int>>> adj_fields(MAX_N);
map <pair <int, int>, vector <int>> edge_adj;
int fields_crossed_by_fields[MAX_N], min_reach_val[MAX_N];
map <pair <int, int>, bool> edges_visited;
map <pair <int, int>, int>fields_crossed_by_walls;
bool is_member[MAX_N], visited[MAX_N];
int main()
{
int M, N, L;
cin >> M >> N >> L;
for (int i = 0; i < L; i++){
int x;
cin >> x;
is_member[x] = true;
}
for (int field = 1; field <= M; field++){
int I;
cin >> I;
vector <int> towns(I);
for (int j = 0; j < I; j++)
cin >> towns[j];
if (towns[0] < towns[I-1])
edge_adj[{towns[0], towns[I-1]}].push_back(field);
else
edge_adj[{towns[I-1], towns[0]}].push_back(field);
for (int j = 0; j < I-1; j++){
if (towns[j] < towns[j+1])
edge_adj[{towns[j], towns[j+1]}].push_back(field);
else
edge_adj[{towns[j+1], towns[j]}].push_back(field);
}
}
for (auto i : edge_adj){
for (auto j : i.second){
adj_fields[j].push_back(i.first);
}
}
int min_crossing_sum = INT_MAX, region = 0;
for (int field = 1; field <= M; field++){
int sum = 0;
queue <pair <int , int>> q;
q.push({field, 0});
fill(visited, visited+MAX_N, false);
fill(fields_crossed_by_fields, fields_crossed_by_fields+MAX_N, 0);
fill(min_reach_val, min_reach_val+MAX_N, INT_MAX);
edges_visited.clear();
fields_crossed_by_walls.clear();
visited[field] = true;
while (!q.empty()){
int a = q.front().first, b = q.front().second;
q.pop();
if (b == 0){ //is a field
for (auto i : adj_fields[a]){ //field to wall
if (edges_visited[i])
continue;
edges_visited[i] = true;
fields_crossed_by_walls[i] = fields_crossed_by_fields[a];
q.push(i);
}
}else{ //is a wall
for (auto i : edge_adj[{a, b}]){ // wall to field
if (visited[i])
continue;
visited[i] = true;
q.push({i, 0});
fields_crossed_by_fields[i] = fields_crossed_by_walls[{a, b}] + 1;
}
}
}
for (int i = 1; i <= M; i++){
for (auto j : adj_fields[i]){
if (is_member[j.first])
min_reach_val[j.first] = min(min_reach_val[j.first], fields_crossed_by_fields[i]);
if (is_member[j.second])
min_reach_val[j.second] = min(min_reach_val[j.second], fields_crossed_by_fields[i]);
}
}
for (int i = 0; i < MAX_N; i++){
if (is_member[i])
sum += min_reach_val[i];
}
if (sum < min_crossing_sum){
min_crossing_sum = sum;
region = field;
}
}
cout << min_crossing_sum << '\n' << region << '\n';
return 0;
}
Comments