Skip to content

Instantly share code, notes, and snippets.

@tqn
Last active December 12, 2016 07:35
Show Gist options
  • Save tqn/9edfe3797d57e5c5028e5c891e221f9b to your computer and use it in GitHub Desktop.
Save tqn/9edfe3797d57e5c5028e5c891e221f9b to your computer and use it in GitHub Desktop.
USACO Platinum Problem #1 (http://usaco.org/index.php?page=viewproblem2&cpid=576) with time complexity O(n^2) (too slow)
#include <algorithm>
#include <ctime>
#include <fstream>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// whether to use breadth-first search or dijkstra's algorithm
#define BFS_OR_DIJKSTRA true
// We have to use a multigraph to model the pipes and stalls
class node;
class edge;
class multigraph {
public:
std::vector<node*> nodes;
std::vector<edge*> edges;
~multigraph();
bool operator==(const multigraph&);
void add_edge(edge* e);
};
class node {
public:
std::vector<edge*> edges;
// unique to this problem
int pressure;
node();
bool operator==(const node&);
void add_edge(edge* e);
};
class edge {
public:
node* vertex1;
node* vertex2;
edge(node*, node*);
bool operator==(const edge&);
};
multigraph::~multigraph() {
for (node* n : nodes) {
delete n;
}
for (edge* e : edges) {
delete e;
}
}
node::node() {
pressure = 0;
}
edge::edge(node* v1, node* v2) {
vertex1 = v1;
vertex2 = v2;
}
bool multigraph::operator==(const multigraph& o) {
return this == &o;
}
bool node::operator==(const node& o) {
return this == &o;
}
void multigraph::add_edge(edge* e) {
edges.push_back(e);
}
void node::add_edge(edge* e) {
edges.push_back(e);
}
bool edge::operator==(const edge& o) {
return this == &o;
}
std::vector<std::string> split_by_space(std::string s) {
std::vector<std::string> result;
std::stringstream ss(s);
std::string item;
while (std::getline(ss, item, ' ')) {
result.push_back(item);
}
return result;
}
int main(int argc, char* argv[])
{
// TODO DEBUG
// time the program
clock_t begin = clock();
// problem parameters
int n, k;
multigraph graph;
std::vector<std::pair<node*, node*>> endpoints;
// we don't need to store the paths because we only use them once
// Read in the input file
std::ifstream input_file("maxflow.in");
if (input_file.is_open()) {
std::string line;
// get first line N K
if (std::getline(input_file, line)) {
std::vector<std::string> split = split_by_space(line);
n = stoi(split[0]);
k = stoi(split[1]);
}
// create N nodes
for (int i = 0; i < n; i++) {
node* new_node = new node();
graph.nodes.push_back(new_node);
}
// edges
for (int i = 0; i < n - 1 && std::getline(input_file, line); i++) {
std::vector<std::string> split = split_by_space(line);
node* node1 = graph.nodes[stoi(split[0]) - 1];
node* node2 = graph.nodes[stoi(split[1]) - 1];
edge* e = new edge(node1, node2);
node1->add_edge(e);
node2->add_edge(e);
graph.add_edge(e);
}
// endpoints
for (int i = 0; i < k && std::getline(input_file, line); i++) {
std::vector<std::string> split = split_by_space(line);
node* endpoint1 = graph.nodes[stoi(split[0]) - 1];
node* endpoint2 = graph.nodes[stoi(split[1]) - 1];
endpoints.push_back(std::make_pair(endpoint1, endpoint2));
}
}
input_file.close();
// search
// copy graph.nodes to a vector of pointers
std::vector<node*> nodes;
for (node* n : graph.nodes) {
nodes.push_back(n);
}
// for each first point in the endpoints of paths search for optimal path
std::vector<std::vector<node*>> paths;
for (auto& p : endpoints) {
#if BFS_OR_DIJKSTRA
// initialization
node* source = p.first;
node* target = p.second;
// distance from source to node
std::unordered_map<node*, int> dist;
// previous node on the path from the source
std::unordered_map<node*, node*> prev;
std::queue<node*> q_next;
for (node* n : nodes) {
dist[n] = std::numeric_limits<int>::max(); // unknown
prev[n] = nullptr; // unknown
}
dist[source] = 0;
q_next.push(source);
std::vector<node*> path;
while (!q_next.empty() && path.empty()) {
node* u = q_next.front();
q_next.pop();
// found path, construct it
if (u == target) {
// current node
node* c = target;
// while there is a previous node
while (prev.at(c)) {
path.insert(path.begin(), c);
c = prev.at(c);
}
path.insert(path.begin(), c);
continue;
}
for (size_t i = 0; i < u->edges.size(); i++) {
auto e = u->edges[i];
// neighbor
node* v = e->vertex1 == u ? e->vertex2 : e->vertex1;
if (dist[v] == std::numeric_limits<int>::max()) {
dist[v] = dist[u] + 1;
prev[v] = u;
q_next.push(v);
}
}
}
paths.push_back(path);
#else
// unvisited nodes
std::unordered_set<node*> unvisited;
// distance from source to node
std::unordered_map<node*, int> dist;
// previous node on the path from the source
std::unordered_map<node*, node*> prev;
node* source = p.first;
node* target = p.second;
// begin the actual algorithm
for (node* n : nodes) {
dist[n] = std::numeric_limits<int>::max(); // unknown
prev[n] = nullptr; // unknown
unvisited.insert(n);
}
dist[source] = 0;
std::vector<node*> path;
while (unvisited.size() != 0 && path.size() == 0) {
// select node with minimum distance
node* u = *std::min_element(
unvisited.begin(),
unvisited.end(),
[&dist](node* const a, node* const b) {
return dist[a] < dist[b];
}
);
unvisited.erase(u);
// found path, construct it
if (u == target) {
// current node
node* c = target;
// while there is a previous node
while (prev.at(c)) {
path.insert(path.begin(), c);
c = prev.at(c);
}
path.insert(path.begin(), c);
}
// iterate over neighbors
// for each doesn't work for some reason
for (size_t i = 0; i < u->edges.size(); i++) {
auto e = u->edges[i];
// neighbor
node* v = e->vertex1 == u ? e->vertex2 : e->vertex1;
// alternative path
auto alt = dist[u] + 1; // 1 because in this problem each edge is 1 long
// better path?
if (alt < dist[v]) {
dist[v] = alt;
prev[v] = u;
}
}
}
paths.push_back(path);
#endif
}
// add pressure to each node
for (auto& path : paths) {
for (node* n : path) {
n->pressure++;
}
}
// find the maximum right side value in `pressure`
node* max_pressure = *std::max_element(
graph.nodes.begin(),
graph.nodes.end(),
[](node* const a, node* const b) {
return a->pressure < b->pressure;
}
);
// TODO DEBUG
const static auto node_number = [&graph](node* n) -> int {
return std::find(graph.nodes.begin(), graph.nodes.end(), n) - graph.nodes.begin() + 1;
};
std::cout << "time: " << (int)(((double)(clock() - begin) / CLOCKS_PER_SEC) * 1000) << "ms" << std::endl;
std::cout << "# nodes: " << graph.nodes.size() << std::endl;
std::cout << "# edges: " << graph.edges.size() << std::endl;
std::cout << "# endpoints: " << endpoints.size() << std::endl;
std::cout << "# paths: " << paths.size() << std::endl;
std::cout
<< "solution: node "
<< node_number(max_pressure)
<< ": "
<< max_pressure->pressure
<< std::endl;
// print to output file
std::ofstream of("maxflow.out", std::ios::trunc); // remove the contents of the file
of << max_pressure->pressure << std::endl;
of.close();
return 0;
}
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment