Pagini recente » Cod sursa (job #1880119) | Cod sursa (job #1570563) | Cod sursa (job #796738) | Cod sursa (job #2579147) | Cod sursa (job #3188751)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define MAX_N 105
#define MAX_M 10005
#define LARGE_NUMBER 1e9
ifstream input("harta.in");
ofstream output("harta.out");
int n, dist[MAX_M], parent[MAX_M], capacity[MAX_M][MAX_M];
vector<pair<int, int>> roads;
vector<int> cities[MAX_N + 5];
bool dijkstra() {
queue<int> q;
q.push(0);
dist[0] = 0;
// Perform BFS until the destination is reached
while (!q.empty()) {
int current = q.front();
q.pop();
// or no more augmenting paths are found
if (current == 2 * n + 1)
break;
for (auto next : cities[current]) {
// If there is capacity on the edge and the new path is shorter
if (capacity[current][next] && dist[next] > dist[current] + 1) {
dist[next] = dist[current] + 1;
parent[next] = current;
q.push(next);
}
}
}
// no augmenting path is found
if (dist[2 * n + 1] >= LARGE_NUMBER)
return false;
int flow = LARGE_NUMBER;
// Find the minimum capacity on the augmenting path
for (int current = 2 * n + 1; current; current = parent[current])
flow = min(flow, capacity[parent[current]][current]);
// Update the residual graph along the augmenting path
for (int current = 2 * n + 1; current; current = parent[current]) {
capacity[parent[current]][current] -= flow;
capacity[current][parent[current]] += flow;
}
return true;
}
void buildGraph() {
for (int i = 1; i <= n; ++i) {
int outRoads, inRoads;
input >> outRoads >> inRoads;
cities[0].push_back(i);
cities[i].push_back(0);
capacity[0][i] = outRoads;
cities[i + n].push_back(2 * n + 1);
cities[2 * n + 1].push_back(i + n);
capacity[i + n][2 * n + 1] = inRoads;
}
// Add edges between cities
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j) {
cities[i].push_back(j + n);
cities[j + n].push_back(i);
capacity[i][j + n] = 1;
}
}
}
}
void findRoads() {
while (dijkstra());
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j && !capacity[i][j + n]) {
roads.push_back({i, j});
}
}
}
}
int main() {
input >> n;
buildGraph();
findRoads();
output << roads.size() << '\n';
for (auto road : roads) {
output << road.first << ' ' << road.second << '\n';
}
return 0;
}