Pagini recente » Cod sursa (job #1387460) | Cod sursa (job #2276350) | Cod sursa (job #3195590) | Cod sursa (job #1402858) | Cod sursa (job #2962532)
#include <bits/stdc++.h>
using namespace std;
// COMPLEXITATE TIMP: O(E*F)
// E = muchii
// F = maxflow
#define NMAX 203
#define INF 0x3f3f3f3f
ifstream fin("harta.in");
ofstream fout("harta.out");
int N, c[NMAX][NMAX], f[NMAX][NMAX], nr_iteratii, d[NMAX], pred[NMAX];
vector <int> coada;
void bf()
{
int v, i;
vector <int> ::iterator it;
d[1] = nr_iteratii;
coada.push_back(1);
while (!coada.empty())
{
it = coada.end() - 1;
v = *it;
coada.pop_back();
for (i = 1; i <= 2 * N + 2; ++i)
if (c[v][i] > f[v][i] && d[i] != nr_iteratii)
{
d[i] = nr_iteratii;
pred[i] = v;
coada.push_back(i);
}
}
}
void algoritm(int s, int t)
{
int min, i;
++nr_iteratii;
while (d[t] != nr_iteratii)
{
min = INF;
bf();
if (d[t] != nr_iteratii)
break;
i = t;
while (pred[i])
{
if (min > c[pred[i]][i] - f[pred[i]][i])
min = c[pred[i]][i] - f[pred[i]][i];
i = pred[i];
}
i = t;
while (pred[i])
{
f[pred[i]][i] += min;
f[i][pred[i]] -= min;
i = pred[i];
}
++nr_iteratii;
}
}
int main()
{
int x, y, gt = 0;
fin >> N;
for (int i = 1; i <= N; ++i)
{
fin >> x >> y;
gt += x;
c[1][i + 1] = x;
c[N + i + 1][2 * N + 2] = y;
}
for (int i = 2; i <= N + 1; ++i)
for (int j = N + 2; j <= 2 * N + 1; ++j)
if (i + N != j)
c[i][j] = 1;
algoritm(1, 2 * N + 2);
fout << gt << '\n';
for (int i = 2; i <= N + 1; ++i)
for (int j = N + 2; j <= 2 * N + 1; ++j)
if (f[i][j])
fout << i - 1 << " " << j - N - 1 << '\n';
return 0;
}