Pagini recente » Cod sursa (job #2352921) | Cod sursa (job #1667186) | Cod sursa (job #2347217) | Cod sursa (job #716654) | Cod sursa (job #3191473)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int MAX_N = 205;
int n;
vector<vector<int>> graph(MAX_N);
int capacity[MAX_N][MAX_N];
int initial_capacity[MAX_N][MAX_N];
int visited[MAX_N], parent[MAX_N];
int bfs() {
queue<int> q;
q.push(0);
fill(begin(parent), end(parent), -1);
fill(begin(visited), end(visited), 0);
visited[0]++;
while (!q.empty()) {
int current_node = q.front();
if (current_node == 2 * n + 1)
return 1;
for (int i = 0; i < graph[current_node].size(); i++) {
int next_node = graph[current_node][i];
if (capacity[current_node][next_node] > 0 && !visited[next_node]) {
visited[next_node]++;
parent[next_node] = current_node;
q.push(next_node);
}
}
q.pop();
}
return 0;
}
int edmondsKarp() {
int max_flow = 0;
while (bfs()) {
for (int i = 0; i < graph[2 * n + 1].size(); i++) {
int current_node = graph[2 * n + 1][i];
if (capacity[current_node][2 * n + 1] > 0 && visited[current_node]) {
vector<int> path;
path.push_back(current_node);
while (parent[current_node] != -1) {
current_node = parent[current_node];
path.push_back(current_node);
}
int min_capacity = INT_MAX;
for (int i = 0; i < path.size(); i++)
if (i == 0)
min_capacity = min(min_capacity, capacity[path[i]][2 * n + 1]);
else
min_capacity = min(min_capacity, capacity[path[i]][path[i - 1]]);
max_flow += min_capacity;
for (int i = 0; i < path.size(); i++) {
if (i == 0) {
capacity[path[i]][2 * n + 1] -= min_capacity;
capacity[2 * n + 1][path[i]] += min_capacity;
}
else {
capacity[path[i]][path[i - 1]] -= min_capacity;
capacity[path[i - 1]][path[i]] += min_capacity;
}
}
}
}
}
return max_flow;
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
fin >> x >> y;
graph[0].push_back(i);
capacity[0][i] = x;
initial_capacity[0][i] = x;
graph[n + i].push_back(2 * n + 1);
graph[2 * n + 1].push_back(n + i);
capacity[n + i][2 * n + 1] = y;
initial_capacity[n + i][2 * n + 1] = y;
}
for (int i = 1; i <= n; i++)
for (int j = n + 1; j < 2 * n + 1; j++)
if ((i + n) != j) {
graph[i].push_back(j);
graph[j].push_back(i);
capacity[i][j] = 1;
initial_capacity[i][j] = 1;
}
fout << edmondsKarp() << "\n";
for (int i = 1; i <= n; i++)
for (int j = n + 1; j < 2 * n + 1; j++)
if (initial_capacity[i][j] == 1 && capacity[i][j] == 0)
fout << i << " " << j - n << "\n";
return 0;
}