Pagini recente » Cod sursa (job #2336494) | Cod sursa (job #1682483) | Cod sursa (job #1589570) | Cod sursa (job #1776191) | Cod sursa (job #2956025)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int dim = 105;
int n, deg_in[2*dim], deg_out[2*dim];
vector<int> vec[dim];
int graf_rezidual[2*dim][2*dim];
queue<int> q;
int viz[2*dim];
int tata[2*dim];
int sursa, destinatie;
int BFS() {
for (int i=0; i<=2*n+1; i++) {
viz[i] = 0;
}
viz[sursa] = 1;
q.push(sursa);
tata[sursa] = -1;
while (!q.empty()) {
int x = q.front();
q.pop();
if (x == destinatie) continue;
for (auto y:vec[x]) {
if (graf_rezidual[x][y] > 0 && !viz[y]) {
viz[y] = 1;
tata[y] = x;
q.push(y);
}
}
}
return viz[destinatie];
}
int main() {
in >> n;
for (int i=1; i<=n; i++) {
in >> deg_out[i] >> deg_in[i];
}
sursa = 0;
destinatie = 2*n + 1;
for (int i=1; i<=n; i++) {
vec[sursa].push_back(i);
vec[i].push_back(sursa);
graf_rezidual[sursa][i] = deg_out[i];
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (i != j) {
vec[i].push_back(n + j);
vec[n+j].push_back(i);
graf_rezidual[i][n+j] = 1;
}
}
}
for (int i=1; i<=n; i++) {
vec[i+n].push_back(destinatie);
vec[destinatie].push_back(i+n);
graf_rezidual[i+n][destinatie] = deg_in[i];
}
int maxflow = 0;
int mini = INT32_MAX;
while (BFS()) {
for (auto y:vec[destinatie]) {
mini = INT32_MAX;
tata[destinatie] = y;
for (int j = destinatie; j != sursa; j = tata[j]) {
mini = min(mini, graf_rezidual[tata[j]][j]);
}
maxflow += mini;
for (int j = destinatie; j != sursa; j = tata[j]) {
graf_rezidual[tata[j]][j] -= mini;
graf_rezidual[j][tata[j]] += mini;
}
}
}
out << maxflow << "\n";
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (i != j && graf_rezidual[i][n+j] == 0) {
out << i << " " << j << "\n";
}
}
}
return 0;
}