Pagini recente » Cod sursa (job #103059) | Cod sursa (job #339291) | Cod sursa (job #2833395) | Cod sursa (job #2738501) | Cod sursa (job #183149)
Cod sursa(job #183149)
#include <stdio.h>
#include <string.h>
int n, c[202][202], source, sink, t[202], f[202][202];
int min(int x, int y) { return x < y ? x : y; }
int BF()
{
int i, q[202], p, u;
memset(t,0,sizeof(t));
q[1] = source; p = u = 1;
while (p <= u)
{
for (i = 1; i <= 2 * n + 1; i++)
if (c[q[p]][i] - f[q[p]][i] > 0 && !t[i])
{
q[++u] = i;
t[i] = q[p];
if (i == sink) return 1;
}
p++;
}
return 0;
}
void flux()
{
int i, j, r;
while (BF())
{
r = 30000;
i = sink;
while (i != source)
{
r = min(r,c[t[i]][i] - f[t[i]][i]);
i = t[i];
}
i = sink;
while (i != source)
{
f[t[i]][i] += r;
f[i][t[i]] -= r;
i = t[i];
}
}
for (i = 1; i <= n; i++)
for (j = n + 1; j <= 2 * n; j++)
if (f[i][j] == 1) printf("%d %d\n",i,j-n/2);
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
int i, j, x, y, s = 0;
scanf("%d",&n);
source = 0;
sink = 2 * n + 1;
for (i = 1; i <= n; i++)
{
scanf("%d %d", &x, &y);
c[source][i] = x;
c[i + n][sink] = y;
s += x;
}
printf("%d\n",s);
for (i = 1; i <= n; i++)
{
for (j = n + 1; j <= 2 * n; j++) c[i][j] = 1;
c[i][i + n] = 0;
}
flux();
return 0;
}