diff options
Diffstat (limited to '05-advanced_algorithms_and_complexity')
3 files changed, 335 insertions, 35 deletions
diff --git a/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp b/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp index db0dfe8..f6b857b 100644 --- a/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp +++ b/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp @@ -1,7 +1,10 @@ #include <iostream> #include <vector> +#include <queue> +#include <limits> using std::vector; +using std::queue; /* This class implements a bit unusual scheme for storing edges of the graph, * in order to retrieve the backward edge for a given edge quickly. */ @@ -71,6 +74,49 @@ FlowGraph read_data() { int max_flow(FlowGraph& graph, int from, int to) { int flow = 0; + + queue<int> q; + + for (;;) { + vector<int> pred(graph.size(), -1); + q.push(from); + while(!q.empty()) { + int node = q.front(); + q.pop(); + auto edges = graph.get_ids(node); + for (int i = 0; i < edges.size(); i++) { + const FlowGraph::Edge& edge = graph.get_edge(edges[i]); + if (pred[edge.to] == -1 && edge.to != from && edge.capacity > edge.flow) { + pred[edge.to] = edges[i]; + q.push(edge.to); + } + } + } + if (pred[to] == -1) + break; + + /* std::cout << from << " -> " << to << std::endl; */ + /* for (int i = 0; i < pred.size(); i++) */ + /* std::cout << pred[i] << " "; */ + /* std::cout << std::endl; */ + /* break; */ + + int df = std::numeric_limits<int>::max(); + for (int e = pred[to]; e != -1; e = pred[e]) { + const FlowGraph::Edge& edge = graph.get_edge(e); + /* std::cout << edge.from << " -> " << edge.to << std::endl; */ + df = std::min(df, edge.capacity - edge.flow); + e = edge.from; + } + + for (int e = pred[to]; e != -1; e = pred[e]) { + const FlowGraph::Edge& edge = graph.get_edge(e); + graph.add_flow(e, df); + e = edge.from; + } + + flow += df; + } return flow; } diff --git a/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp b/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp index 46765ea..d81c09a 100644 --- a/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp +++ b/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp @@ -2,10 +2,96 @@ #include <vector> #include <algorithm> #include <memory> +#include <stack> using std::vector; +using std::stack; using std::cin; using std::cout; +using std::endl; + +/* #define DEBUG */ + +class FlowGraph { +public: + struct Edge { + int from, to; + }; + +private: + vector<Edge> edges; + vector<bool> full; + vector<vector<size_t>> graph; + vector<bool> visited; + +public: + explicit FlowGraph(size_t n): graph(n) { } + + void add_edge(int from, int to) { + Edge forward_edge = {from, to}; + Edge backward_edge = {to, from}; + graph[from].push_back(edges.size()); + edges.push_back(forward_edge); + graph[to].push_back(edges.size()); + edges.push_back(backward_edge); + full.push_back(false); + full.push_back(true); + } + + size_t size() const { + return graph.size(); + } + + const vector<size_t>& get_ids(int from) const { + return graph[from]; + } + + const Edge& get_edge(size_t id) const { + return edges[id]; + } + + const bool isFull(size_t id) const { + return full[id]; + } + + void print_edge(size_t id) const { + const Edge& e = get_edge(id); + cout << " " << e.from << "->" << e.to << " " << full[id] << endl; + } + + void use(size_t id) { + full[id] = !full[id]; + full[id ^ 1] = !full[id ^ 1]; + } + + void dfs(int from, int to, vector<size_t>& path) { + path.clear(); + visited.clear(); + visited.resize(graph.size(), false); + _dfs(from, to, path); + } + +private: + bool _dfs(int from, int to, vector<size_t>& path) { + visited[from] = true; + + if (from == to) + return true; + + const vector<size_t>& ids = get_ids(from); + for (auto id : ids) { + if (!full[id]) { + int next = edges[id].to; + if (!visited[next] && _dfs(next, to, path)) { + path.push_back(id); + return true; + } + } + } + + return false; + } +}; class MaxMatching { public: @@ -41,19 +127,85 @@ class MaxMatching { cout << "\n"; } - vector<int> FindMatching(const vector<vector<bool>>& adj_matrix) { - // Replace this code with an algorithm that finds the maximum - // matching correctly in all cases. + vector<int> FindMatching(const vector<vector<bool>>& adj_matrix) + { int num_left = adj_matrix.size(); int num_right = adj_matrix[0].size(); + +#ifdef DEBUG + cout << "matrix" << endl; + for (int i = 0; i < num_left; i++) { + for (int j = 0; j < num_right; j++) + cout << adj_matrix[i][j] << " "; + cout << endl; + } + cout << " ---" << endl; +#endif + + FlowGraph graph(num_left + num_right + 2); + int source = graph.size() - 2; + int sink = source + 1; + + for (int i = 0; i < num_left; i++) + graph.add_edge(source, i); + for (int i = num_left; i < num_left + num_right; i++) + graph.add_edge(i, sink); + + for (int i = 0; i < num_left; i++) { + for (int j = 0; j < num_right; j++) { + if (adj_matrix[i][j]) + graph.add_edge(i, num_left + j); + } + } +#ifdef DEBUG + cout << "graph : " << endl; + for (int i = 0; i < graph.size(); i++) { + const vector<size_t>& ids = graph.get_ids(i); + for (int j = 0; j < ids.size(); j++) + graph.print_edge(ids[j]); + cout << endl; + } +#endif + + vector<size_t> edges; + for(;;) { + + graph.dfs(source, sink, edges); + + if (edges.size() == 0) + break; +#ifdef DEBUG + cout << "path : " << endl; + for (auto eid : edges) + graph.print_edge(eid); + cout << endl; +#endif + + for (auto e : edges) + graph.use(e); + +#ifdef DEBUG + cout << "graph : " << endl; + for (int i = 0; i < graph.size(); i++) { + const vector<size_t>& ids = graph.get_ids(i); + for (int j = 0; j < ids.size(); j++) + graph.print_edge(ids[j]); + cout << endl; + } +#endif + } + vector<int> matching(num_left, -1); - vector<bool> busy_right(num_right, false); - for (int i = 0; i < num_left; ++i) - for (int j = 0; j < num_right; ++j) - if (matching[i] == -1 && !busy_right[j] && adj_matrix[i][j]) { - matching[i] = j; - busy_right[j] = true; + for (int i = 0; i < num_left; i++) { + const vector<size_t>& ids = graph.get_ids(i); + for (auto& eid : ids) { + if (graph.isFull(eid)) { + const FlowGraph::Edge& edge = graph.get_edge(eid); + if (edge.to != source) + matching[edge.from] = edge.to - num_left; + } } + } return matching; } }; diff --git a/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp b/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp index 2a70c87..a6cca51 100644 --- a/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp +++ b/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp @@ -7,6 +7,97 @@ using std::vector; using std::cin; using std::cout; +class FlowGraph { +public: + struct Edge { + int from, to; + }; + +private: + vector<Edge> edges; + vector<bool> full; + vector<vector<size_t>> graph; + vector<bool> visited; + +public: + explicit FlowGraph(size_t n): graph(n) { } + + void add_edge(int from, int to) { + Edge forward_edge = {from, to}; + Edge backward_edge = {to, from}; + graph[from].push_back(edges.size()); + edges.push_back(forward_edge); + graph[to].push_back(edges.size()); + edges.push_back(backward_edge); + full.push_back(false); + full.push_back(true); + } + + size_t size() const { + return graph.size(); + } + + const vector<size_t>& get_ids(int from) const { + return graph[from]; + } + + const Edge& get_edge(size_t id) const { + return edges[id]; + } + + const bool isFull(size_t id) const { + return full[id]; + } + + void print_edge(size_t id) const { + const Edge& e = get_edge(id); + cout << " " << e.from << "->" << e.to << " " << full[id] << "\n"; + } + + void print() { + cout << "graph : " << "\n"; + for (int i = 0; i < size(); i++) { + const vector<size_t>& ids = get_ids(i); + for (int j = 0; j < ids.size(); j++) + print_edge(ids[j]); + cout << "\n"; + } + } + + void use(size_t id) { + full[id] = !full[id]; + full[id ^ 1] = !full[id ^ 1]; + } + + void dfs(int from, int to, vector<size_t>& path) { + path.clear(); + visited.clear(); + visited.resize(graph.size(), false); + _dfs(from, to, path); + } + +private: + bool _dfs(int from, int to, vector<size_t>& path) { + visited[from] = true; + + if (from == to) + return true; + + const vector<size_t>& ids = get_ids(from); + for (auto id : ids) { + if (!full[id]) { + int next = edges[id].to; + if (!visited[next] && _dfs(next, to, path)) { + path.push_back(id); + return true; + } + } + } + + return false; + } +}; + class StockCharts { public: void Solve() { @@ -32,35 +123,46 @@ class StockCharts { } int MinCharts(const vector<vector<int>>& stock_data) { - // Replace this incorrect greedy algorithm with an - // algorithm that correctly finds the minimum number - // of charts on which we can put all the stock data - // without intersections of graphs on one chart. - - int num_stocks = stock_data.size(); - // Vector of charts; each chart is a vector of indices of individual stocks. - vector<vector<int>> charts; - for (int i = 0; i < stock_data.size(); ++i) { - bool added = false; - for (auto& chart : charts) { - bool can_add = true; - for (int index : chart) - if (!compare(stock_data[i], stock_data[index]) && - !compare(stock_data[index], stock_data[i])) { - can_add = false; - break; + int sz = stock_data.size(); + + FlowGraph graph(2 * sz + 2); + int source = graph.size() - 2; + int sink = source + 1; + + + for (int i = 0; i < sz; i++) { + for (int j = 0; j < sz; j++) { + // j is strictly above i + if (compare(stock_data[i], stock_data[j])) + graph.add_edge(i, sz + j); } - if (can_add) { - chart.push_back(i); - added = true; - break; - } } - if (!added) { - charts.emplace_back(vector<int>{i}); + + for (int i = 0; i < sz; i++) { + graph.add_edge(source, i); + graph.add_edge(sz + i, sink); } - } - return charts.size(); + + /* graph.print(); */ + + vector<size_t> edges; + for(;;) { + + graph.dfs(source, sink, edges); + + if (edges.size() == 0) + break; + + for (auto e : edges) + graph.use(e); + } + + int ret = 0; + for (auto& eid : graph.get_ids(source)) { + if (!graph.isFull(eid)) + ret += 1; + } + return ret; } bool compare(const vector<int>& stock1, const vector<int>& stock2) { |