Pagini recente » Cod sursa (job #1912318) | Cod sursa (job #3234200) | Cod sursa (job #354647) | Cod sursa (job #3225214) | Cod sursa (job #2964565)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <iterator>
using namespace std;
int n, max_flow;
vector<vector<int>> adjacence_list;
vector <vector <int>> cap;
vector <int> root;
ifstream f("harta.in");
ofstream g("harta.out");
bool bfs() {
root = vector<int>(2 * n + 2, 0);
vector<bool>visited(2 * n + 2);
queue <int> q;
q.push(0);
visited[0] = true;
while (!q.empty()) {
int nod = q.front();
q.pop();
for (auto vecin : adjacence_list[nod]) {
int current_cap = cap[nod][vecin];
if (current_cap > 0 && !visited[vecin]) {
root[vecin] = nod;
if (vecin == 2 * n + 1)
return true;
visited[vecin] = true;
q.push(vecin);
}
}
}
return false;
}
int edmonds_karp_algorithm() {
while (bfs()) {
int current_flow = INT_MAX;
int i = 2 * n + 1;
while (i != 0) {
current_flow = min(current_flow, cap[root[i]][i]);
i = root[i];
}
i = 2 * n + 1;
while (i != 0) {
cap[root[i]][i] -= current_flow;
cap[i][root[i]] += current_flow;
i = root[i];
}
max_flow += current_flow;
}
return max_flow;
}
int main()
{
int x, y;
f >> n;
adjacence_list = vector<vector<int>>(2*n+2);
root = vector<int>(2*n+2, 0);
cap = vector<vector<int>>(2 * n + 2, vector <int>(2 * n + 2, 0));
for(int i=1;i<=n;i++)
for (int j = n + 1;j <= 2 * n;j++) {
if (i != j - n) {
adjacence_list[i].push_back(j);
adjacence_list[j].push_back(i);
cap[i][j] = 1;
}
}
for (int i = 1;i <= n;i++)
{
f >> x >> y;
adjacence_list[0].push_back(i);
adjacence_list[i].push_back(0);
adjacence_list[2 * n + 1].push_back(i+n);
adjacence_list[i+n].push_back(2 * n + 1);
cap[0][i] = x;
cap[i+n][2*n+1] = y;
}
g << edmonds_karp_algorithm() << endl;
for (int i = 1;i <= n;i++)
for (int j = n + 1;j <= 2 * n;j++)
if (cap[j][i])
g << i << " " << j - n << endl;
return 0;
}