Pagini recente » Cod sursa (job #2281235) | Cod sursa (job #2446317) | Cod sursa (job #2956493) | Cod sursa (job #62423) | Cod sursa (job #183275)
Cod sursa(job #183275)
#include <stdio.h>
#include <string.h>
int n, c[202][202], source, sink, t[202], f[202][202], viz[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));
memset(viz,0,sizeof(viz));
q[1] = source; p = u = 1;
viz[0] = 1;
while (p <= u)
{
for (i = 1; i <= 2 * n + 1; i++)
if (c[q[p]][i] - f[q[p]][i] > 0 && !t[i] && !viz[i])
{
q[++u] = i;
t[i] = q[p];
if (i == sink) return 1;
viz[i] = 1;
}
p++;
}
return 0;
}
void flux()
{
int i, j, ok;
while (BF())
{
for(i = source; i < sink; i++)
{
if(t[i]==-1 || c[i][sink] <= 0)continue;
ok = 1;
for(j = i; j != source && j != -1; j = t[j])
if(c[t[j]][j] == 0) { ok = 0; break;}
if(!ok) continue;
c[i][sink] -= 1;
c[sink][i] += 1;
for(j = i; j != source; j = t[j])
{
c[t[j]][j] -= 1;
c[j][t[j]] += 1;
}
}
}
for(i = 1;i <= n; i++)
for(j = n + 1; j <= n << 1; j++)
if(!c[i][j] && i != j - n) printf("%d %d\n", i, j - n);
}
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;
}