Pagini recente » Cod sursa (job #604299) | Cod sursa (job #2273645) | Cod sursa (job #138216) | Cod sursa (job #171750) | Cod sursa (job #3179780)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include<climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n;
vector<vector<int>> lista(305);
int cap[205][205];
int cap_init[205][205];
int viz[205], tata[205];
int bfs() {
queue<int> coada;
coada.push(0);
for (int i = 0; i <= 2 * n + 1; i++) {
tata[i] = -1;
viz[i] = 0;
}
viz[0]++;
while (!coada.empty()) {
int nod_cur = coada.front();
if (nod_cur == 2 * n + 1)
return 1;
for (int i = 0; i < lista[nod_cur].size(); i++) {
int nod_vec = lista[nod_cur][i];
if (cap[nod_cur][nod_vec] > 0 && viz[nod_vec] == 0) {
viz[nod_vec]++;
tata[nod_vec] = nod_cur;
coada.push(nod_vec);
}
}
coada.pop();
}
return 0;
}
int Edmonds_Karp() {
int max_flux = 0;
while (bfs()) {
for (int i = 0; i < lista[2 * n + 1].size(); i++) {
int nod_cur = lista[2 * n + 1][i];
if (cap[nod_cur][2 * n + 1] > 0 && viz[nod_cur]) {
vector<int> drum;
drum.push_back(nod_cur);
while (tata[nod_cur] != -1) {
nod_cur = tata[nod_cur];
drum.push_back(nod_cur);
}
int minim = INT_MAX;
for (int i = 0; i < drum.size(); i++)
if (i == 0)
minim = min(minim, cap[drum[i]][2 * n + 1]);
else
minim = min(minim, cap[drum[i]][drum[i - 1]]);
max_flux += minim;
for (int i = 0; i < drum.size(); i++) {
if (i == 0) {
cap[drum[i]][2 * n + 1] -= minim;
cap[2 * n + 1][drum[i]] += minim;
} else {
cap[drum[i]][drum[i - 1]] -= minim;
cap[drum[i - 1]][drum[i]] += minim;
}
}
}
}
}
return max_flux;
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
fin >> x >> y;
lista[0].push_back(i);
cap[0][i] = x;
cap_init[0][i] = x;
lista[n + i].push_back(2 * n + 1);
lista[2 * n + 1].push_back(n + i);
cap[n + i][2 * n + 1] = y;
cap_init[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) {
lista[i].push_back(j);
lista[j].push_back(i);
cap[i][j] = 1;
cap_init[i][j] = 1;
}
fout << Edmonds_Karp() << "\n";
for (int i = 1; i <= n; i++)
for (int j = n + 1; j < 2 * n + 1; j++)
if (cap_init[i][j] == 1 && cap[i][j] == 0)
fout << i << " " << j - n << "\n";
}