Pagini recente » Cod sursa (job #1938882) | Cod sursa (job #2160584) | Cod sursa (job #2048140) | Cod sursa (job #2909087) | Cod sursa (job #2308195)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int nMax = 100, oo = 2000000000;
vector<int> g[2 * nMax + 5];
int n, c[2 * nMax + 5][2 * nMax + 5], viz[2 * nMax + 5], t[2 * nMax + 5], in[nMax + 5], out[nMax + 5], f, flow;
queue<int> q;
int BF() {
memset(viz, 0, sizeof(viz));
viz[0] = 1;
q.push(0);
while (q.size()) {
int dad = q.front();
q.pop();
if (dad == f)
continue;
for (auto i : g[dad]) {
if (viz[i] == 0 && c[dad][i] > 0) {
q.push(i);
viz[i] = 1;
t[i] = dad;
}
}
}
return viz[f];
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> in[i] >> out[i];
}
f = 2 * n + 1;
for (int i = 1; i <= n; i++) {
g[0].push_back(i);
g[i].push_back(0);
g[f].push_back(i + n);
g[i + n].push_back(f);
c[0][i] = in[i];
c[i + n][f] = out[i];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j)
continue;
g[i].push_back(j + n);
g[j + n].push_back(i);
c[i][j + n] = 1;
}
while (BF()) {
int fmin = oo;
for (int i = f; i; i = t[i])
fmin = min(fmin, c[t[i]][i]);
for (int i = f; i; i = t[i]) {
c[t[i]][i] -= fmin;
c[i][t[i]] += fmin;
}
flow += fmin;
}
fout << flow << '\n';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && c[i][n + j] == 0)
fout << i << " " << j << '\n';
return 0;
}