Pagini recente » Cod sursa (job #2557463) | Cod sursa (job #875161) | Cod sursa (job #2748142) | Cod sursa (job #2261073) | Cod sursa (job #3193462)
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
using namespace std;
ifstream input_stream("harta.in");
ofstream output_stream("harta.out");
vector<vector<int>> city_network;
vector<vector<int>> city_flow;
vector<int> path_parents;
vector<bool> visited_cities;
void loadMapData(int& num_cities, int& start_point, int& end_point) {
input_stream >> num_cities;
start_point = 2 * num_cities;
end_point = 2 * num_cities + 1;
city_network.assign(2 * num_cities + 2, vector<int>(2 * num_cities + 2, 0));
city_flow.assign(2 * num_cities + 2, vector<int>(2 * num_cities + 2, 0));
path_parents.assign(2 * num_cities + 2, -1);
visited_cities.assign(2 * num_cities + 2, false);
for (int i = 0; i < num_cities; ++i) {
int outgoing, incoming;
input_stream >> outgoing >> incoming;
city_network[start_point][i] = outgoing;
city_network[i + num_cities][end_point] = incoming;
for (int j = 0; j < num_cities; ++j) {
if (i != j) {
city_network[i][num_cities + j] = 1;
}
}
}
}
bool searchForPath(int start_point, int end_point) {
fill(begin(visited_cities), end(visited_cities), false);
queue<int> city_queue;
city_queue.push(start_point);
visited_cities[start_point] = true;
while (!city_queue.empty()) {
int current_city = city_queue.front();
city_queue.pop();
for (int i = 0; i <= end_point; ++i) {
if (!visited_cities[i] && city_network[current_city][i] - city_flow[current_city][i] > 0) {
path_parents[i] = current_city;
visited_cities[i] = true;
city_queue.push(i);
if (i == end_point) return true;
}
}
}
return false;
}
void exportMapRoutes(int num_cities, int max_flow) {
output_stream << max_flow << endl;
for (int i = 0; i < num_cities; ++i) {
for (int j = 0; j < num_cities; ++j) {
if (city_flow[i][num_cities + j] >
0) {
output_stream << i + 1 << " " << j + 1 << endl;
}
}
}
}
int main() {
int num_cities, start_point, end_point;
loadMapData(num_cities, start_point, end_point);
int max_flow = 0;
while (searchForPath(start_point, end_point)) {
int min_capacity = numeric_limits<int>::max();
for (int city = end_point; city != start_point; city = path_parents[city]) {
int prev_city = path_parents[city];
min_capacity = min(min_capacity, city_network[prev_city][city] - city_flow[prev_city][city]);
}
for (int city = end_point; city != start_point; city = path_parents[city]) {
int prev_city = path_parents[city];
city_flow[prev_city][city] += min_capacity;
city_flow[city][prev_city] -= min_capacity;
}
max_flow += min_capacity;
fill(begin(visited_cities), end(visited_cities), false);
fill(begin(path_parents), end(path_parents), -1);
}
exportMapRoutes(num_cities, max_flow);
input_stream.close();
output_stream.close();
return 0;
}