Pagini recente » Cod sursa (job #1697715) | Cod sursa (job #1153715) | Rating Rodriguez Alcantara (Blue_Bear) | Cod sursa (job #358016) | Cod sursa (job #183148)
Cod sursa(job #183148)
#include <stdio.h>
#include <string.h>
int n, c[201][201], 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 <= 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, ok = 0;
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 / 2; i++)
for (j = n / 2 + 1; j <= 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;
}
n *= 2;
flux();
return 0;
}