Pagini recente » Cod sursa (job #545759) | Cod sursa (job #2906758) | Cod sursa (job #551701) | Cod sursa (job #2391270) | Cod sursa (job #1437902)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int dim = 205;
int N, M, Cc, T[dim], C[dim][dim], F[dim][dim], Q[dim];
vector <int> V[dim];
void addmuc (int a, int b, int c)
{
if (c <= 0)
return;
C[a][b] = c;
V[a].push_back (b);
V[b].push_back (a);
}
int bf ()
{
int p = 0, u = 0, ok = 0, i, n, f;
Q[0] = 0;
for (i = 0; i <= M; i++)
T[i] = -1;
while (p <= u)
{
n = Q[p];
for (i = 0; i < V[n].size(); i++)
{
f = V[n][i];
if (T[f] == -1 && C[n][f] > F[n][f])
{
if (f == M)
{
ok = 1;
continue;
}
Q[++u] = f;
T[f] = n;
}
}
p++;
}
return ok;
}
void cit ()
{
in >> N;
M = N + N + 1;
for (int i = 1, j, x, y; i <= N; i++)
{
in >> x >> y;
Cc += x;
addmuc (0, i, x);
addmuc (N+i, M, y);
for (j = 1; j <= N; j++)
{
if (i != j)
{
addmuc (i, N+j, 1);
}
}
}
}
void flux ()
{
int n, f, m, i;
while ( bf () )
{
for (i = 0; i < V[M].size(); i++)
{
if (T[V[N][i]] == 0)
continue;
f = M;
n = V[M][i];
m = C[n][f] - F[n][f];
while (f != 0)
{
m = min (m, C[n][f] - F[n][f]);
f = n;
n = T[f];
}
f = M;
n = V[M][i];
while (f != 0)
{
F[n][f] += m;
F[f][n] -= m;
f = n;
n = T[f];
}
}
}
}
void afi ()
{
int i, j;
out << Cc << '\n';
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (F[i][j+N] == 1)
out << i << ' ' << j << '\n';
}
int main ()
{
cit ();
flux ();
afi ();
return 0;
}