Цель операции разделить Пандею на две несвязанные части, разрушив всего лишь
одну дорогу (изначально карта Пандеи представляет собой связный граф). Хонтийская разведка уже добыла карты Пандеи, передала их экспертам, которые провели исследование и выяснили стоимость разрушения каждой из дорог страны-противника. Вам передали карту всех дорог вместе со стоимостями их разрушения. Вам нужно выбрать самую дешевую дорогу, удовлетворяющую запросам хонтийцев: предстоящая война еще потребует значительных ресурсов.
В первой строке входа заданы два целых числа n и m количество городов и количество дорог Пандеи соответственно. Дороги в Пандее двусторонние. В каждой из следующих m строк по три числа a, b и c номера начального и конечного горо дов дороги (города нумеруются с единицы) и стоимость разрушения данной дороги. 1 ≤ m, n ≤ 50 000. 1 ≤ a, b ≤ n. a = b. 1 ≤ c ≤ 1 000 000 000.
Выведите единственное число наименьшую стоимость дороги, которую можно разрушить, чтобы нарушить связность Пандеи. Если таких дорог не существует, выведите -1.
Проводится поиск в ширину, чтобы найти так называемые "мосты" - ребра, удаление которых, делает граф несвязным. Затем выбирается тот мост, разрушение которого самое дешевое.
#include<stdio.h>
#include<stack>
#include<vector>
#include<algorithm>
struct NodeCostPair {
int node_;
int cost_;
NodeCostPair(int node, int cost):
node_(node), cost_(cost) {}
};
struct ReturnInfo {
int current_node_;
int prev_node_;
std::vector<NodeCostPair>::const_iterator node_it_;
ReturnInfo(int current_node,
int prev_node,
std::vector<NodeCostPair>::const_iterator node_it):
current_node_(current_node), prev_node_(prev_node), node_it_(node_it) {}
};
struct Edge {
int node_from_;
int node_to_;
int cost_;
Edge(int node_from, int node_to, int cost):
node_from_(node_from), node_to_(node_to), cost_(cost) {}
};
enum Colors {
WHITE = 0,
GRAY = 1,
BLACK = 2
};
template <typename T>
const T& min3(const T& a, const T& b, const T& c) {
return std::min(a, std::min(b, c));
}
const int kMaxNodesNumber = 100000;
void DFS(const std::vector< std::vector<NodeCostPair> >& graph_edges,
std::vector<int>& times_in,
std::vector<int>& min_enter_time,
std::vector<Edge>& dfs_edges) {
std::stack<ReturnInfo> stack_nodes;
std::vector<char> colors(graph_edges.size(), 0);
int current_node = 0; // Begin from the node 0.
int prev_node = -1;
int timer = 0;
times_in.resize(graph_edges.size(), kMaxNodesNumber);
times_in[0] = timer;
min_enter_time.resize(graph_edges.size(), kMaxNodesNumber);
bool go_deeper;
bool exist_not_visited_nodes = true;
std::vector<NodeCostPair>::const_iterator node_next_to_visit =
graph_edges[current_node].begin();
while (exist_not_visited_nodes) {
colors[current_node] = GRAY;
go_deeper = false;
for (/* Loop initialization not needed. */;
node_next_to_visit != graph_edges[current_node].end();
++node_next_to_visit) {
if (node_next_to_visit->node_ != prev_node &&
colors[node_next_to_visit->node_] == GRAY) {
// Back edge.
min_enter_time[current_node]
= min3(times_in[node_next_to_visit->node_],
times_in[current_node],
min_enter_time[current_node]);
}
if (colors[node_next_to_visit->node_] == BLACK) {
// Tree edge.
min_enter_time[current_node]
= min3(min_enter_time[node_next_to_visit->node_],
min_enter_time[current_node],
times_in[current_node]);
}
if (colors[node_next_to_visit->node_] == WHITE) {
dfs_edges.push_back(Edge(current_node,
node_next_to_visit->node_,
node_next_to_visit->cost_));
stack_nodes.push(ReturnInfo(current_node,
prev_node,
node_next_to_visit));
prev_node = current_node;
current_node = node_next_to_visit->node_;
node_next_to_visit = graph_edges[current_node].begin();
++timer;
times_in[current_node] = min_enter_time[current_node] = timer;
go_deeper = true;
break;
}
}
if (!go_deeper) {
colors[current_node] = BLACK;
if (stack_nodes.empty()) {
exist_not_visited_nodes = false;
} else {
// Return to the previous node
current_node = stack_nodes.top().current_node_;
prev_node = stack_nodes.top().prev_node_;
node_next_to_visit = stack_nodes.top().node_it_;
stack_nodes.pop();
}
}
}
}
void ReadGraphEdges(std::vector< std::vector<NodeCostPair> >& graph_edges) {
int nodes_num, edges_num;
scanf("%d %d", &nodes_num, &edges_num);
graph_edges.resize(nodes_num);
int node_from, node_to, cost;
for (int counter = 0; counter < edges_num; ++counter) {
scanf("%d %d %d", &node_from, &node_to, &cost);
graph_edges[node_from - 1].push_back(NodeCostPair(node_to - 1, cost));
graph_edges[node_to - 1].push_back(NodeCostPair(node_from - 1, cost));
}
}
const int kMinCost = -1;
int FindMinBridgeCost(const
std::vector< std::vector<NodeCostPair> >& graph_edges) {
int min_cost = kMinCost;
std::vector<int> times_in;
std::vector<int> min_enter_time;
std::vector<Edge> dfs_edges;
DFS(graph_edges, times_in, min_enter_time, dfs_edges);
for (std::vector<Edge>::const_iterator edge_it = dfs_edges.begin();
edge_it != dfs_edges.end(); ++edge_it) {
if (min_enter_time[edge_it->node_to_] > times_in[edge_it->node_from_]) {
if (min_cost == -1) {
min_cost = edge_it->cost_;
} else {
min_cost = std::min(min_cost, edge_it->cost_);
}
}
}
return min_cost;
}
int main() {
std::vector< std::vector<NodeCostPair> > graph_edges;
ReadGraphEdges(graph_edges);
printf("%d\n", FindMinBridgeCost(graph_edges));
return 0;
}
Комментариев нет:
Отправить комментарий