Pagini recente » Cod sursa (job #835406) | Cod sursa (job #2036455) | Cod sursa (job #2324083) | Cod sursa (job #2914805) | Cod sursa (job #6312)
Cod sursa(job #6312)
#include <stdio.h>
#include <string.h>
#define nmax 202
#define infinit 10000
int n, c[nmax][nmax], used[nmax];
int maxflow();
int bfs();
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
int i, j, a, b;
scanf("%d", &n);
for(i = 1; i <= n; ++i)
{
scanf("%d%d", &a, &b);
c[n + i][nmax - 1] = b;
c[0][i] = a;
}
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
if(i != j)
{
c[i][n + j] = 1;
}
}
}
printf("%d\n", maxflow());
for(i = 1; i <= n; ++i)
{
for(j = n + 1; j <= 2 * n; ++j)
{
if(i != j - n)
{
if(!c[i][j])
{
printf("%d %d\n", i, j - n);
}
}
}
}
return 0;
}
int maxflow()
{
int result = 0, path_cap;
while(1)
{
path_cap = bfs();
if(path_cap)
{
result += path_cap;
}
else
{
break;
}
}
return result;
}
int bfs()
{
int i;
int coada[nmax], last = 1, from[nmax], first = 1, where, path_cap = infinit, prev;
memset(used, 0, sizeof(used));
coada[1] = 0;
for(i = 0; i < nmax; ++i)
{
from[i] = -1;
}
while(first <= last)
{
for(i = 1; i < nmax; ++i)
{
if(c[coada[first]][i] && !used[i])
{
from[i] = coada[first];
coada[++last] = i;
used[i] = 1;
}
}
if(used[nmax - 1])
{
break;
}
++first;
}
where = nmax - 1;
while(from[where] != -1)
{
prev = from[where];
if(path_cap > c[prev][where])
{
path_cap = c[prev][where];
}
where = prev;
}
where = nmax - 1;
while(from[where] != -1)
{
prev = from[where];
c[prev][where] -= path_cap;
c[where][prev] += path_cap;
where = prev;
}
if(path_cap == infinit)
{
return 0;
}
else
{
return path_cap;
}
}