Pagini recente » Cod sursa (job #3292701) | Cod sursa (job #2717902) | Cod sursa (job #418304) | Cod sursa (job #3001537) | Cod sursa (job #3190522)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>
using namespace std;
ifstream inputFile("harta.in");
ofstream outputFile("harta.out");
int N, x, y, roadways;
vector<vector<int>> adjacencyList, capacity, flow;
int source, sink;
vector<int> previous;
void initializePrevious() {
for (int i = 0; i <= sink; i++) {
previous[i] = -1;
}
}
int bfs() {
initializePrevious();
queue<pair<int, int>> q;
q.push({0, INT_MAX});
while (!q.empty()) {
int town = q.front().first, minFlowUntilNow = q.front().second;
q.pop();
for (auto& nextTown : adjacencyList[town]) {
if (previous[nextTown] == -1 && capacity[town][nextTown] > flow[town][nextTown]) {
previous[nextTown] = town;
int residualFlow = capacity[town][nextTown] - flow[town][nextTown];
int minimumFlowOfPath = minFlowUntilNow > residualFlow ? residualFlow : minFlowUntilNow;
q.push({nextTown, minimumFlowOfPath});
if (nextTown == sink) return minimumFlowOfPath;
}
}
}
return 0;
}
void edmondsKarp() {
int town, prevTown;
while (true) {
int flowOfPath = bfs();
if (!flowOfPath) break;
town = sink;
while (source != town) {
prevTown = previous[town];
flow[town][prevTown] -= flowOfPath;
flow[prevTown][town] += flowOfPath;
town = previous[town];
}
}
}
void readData() {
inputFile >> N;
sink = 2 * N + 1;
previous.resize(sink);
adjacencyList.resize(sink + 1, {});
capacity.assign(sink + 1, vector<int>(sink + 1));
flow.resize(sink + 1, vector<int>(sink + 1));
for (int i = 1; i <= N; i++) {
inputFile >> x >> y;
roadways += x;
for (int j = N + 1; j < sink; j++) {
if (i != j - N) {
adjacencyList[j].push_back(i);
adjacencyList[i].push_back(j);
capacity[i][j] = 1;
}
}
capacity[source][i] = x;
capacity[i + N][sink] = y;
adjacencyList[source].push_back(i);
adjacencyList[i].push_back(source);
adjacencyList[i + N].push_back(sink);
adjacencyList[sink].push_back(i + N);
}
}
void solve() {
readData();
outputFile << roadways << endl;
edmondsKarp();
for (int i = 1; i <= N; i++) {
for (int j = N + 1; j < sink; j++) {
if (flow[i][j]) {
outputFile << i << " " << j - N << endl;
}
}
}
}
int main() {
solve();
return 0;
}