Pagini recente » Cod sursa (job #1527098) | Cod sursa (job #159564) | Cod sursa (job #2092206) | Cod sursa (job #240695) | Cod sursa (job #79544)
Cod sursa(job #79544)
#include <stdio.h>
#include <string.h>
#define NMAX 210
#define INFI 0x3f3f3f3f
int n;
int in[NMAX], out[NMAX];
int source, sink;
int c[NMAX][NMAX];
void read()
{
int i;
scanf("%d", &n);
for(i = 1; i <= n; ++i)
scanf("%d%d", out+i, in+i);
}
void init()
{
int i, j;
source = 0, sink = 2*n+1;
for(i = 1; i <= n; ++i)
c[source][i] = out[i], c[i+n][sink] = in[i];
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
if(i != j)
++c[i][j+n];
}
#define MIN(a, b) ((a) < (b)) ? (a) : (b)
int t[NMAX];
int bf()
{
int inc, sf;
int q[NMAX], viz[NMAX];
int i, x;
memset(viz, 0, sizeof(viz));
inc = sf = 1;
q[1] = source;
viz[source] = 1;
while(inc <= sf)
{
x = q[inc++];
for(i = source; i <= sink; ++i)
if(c[x][i] && !viz[i])
{
++viz[i];
q[++sf] = i;
t[i] = x;
if(i == sink)
return 1;
}
}
return 0;
}
void solve()
{
int i;
while(bf())
{
for(i = sink; i != source; i = t[i])
++c[i][t[i]], --c[t[i]][i];
}
}
void print()
{
printf(" \n");
int nr = 0, i, j;
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
if(i != j && !c[i][j+n])
++nr, printf("%d %d\n", i, j);
fseek(stdout, 0, SEEK_SET);
printf("%d", nr);
}
int main()
{
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
read();
init();
solve();
print();
return 0;
}