Pagini recente » Cod sursa (job #897036) | Cod sursa (job #2215260) | Cod sursa (job #1205038) | Cod sursa (job #13826) | Cod sursa (job #141663)
Cod sursa(job #141663)
#include <stdio.h>
#include <values.h>
#define nmax 256
int N, ans;
int viz[nmax], cat[nmax];
int cap[nmax][nmax], nod[nmax*nmax];
void read()
{
int i;
freopen("harta.in", "r", stdin);
scanf("%d", &N);
for (i = 1; i <= N; ++i)
scanf("%d%d", &cap[i+N][N+N+1], &cap[0][i]);
}
int bfs()
{
int i, j, ic, sc, flux;
for (viz[0] = -1, cat[0] = MAXINT, i = 1; i <= N+N+1; ++i)
viz[i] = cat[i] = MAXINT;
nod[ic = sc = 0] = 0;
while (ic <= sc)
{
i = nod[ic++];
for (j = 0; j <= N+N+1; j++)
if (cap[i][j] > 0 && viz[j] == MAXINT)
{
nod[++sc] = j;
viz[j] = i;
cat[j] = cap[i][j] < cat[i]? cap[i][j]: cat[i];
}
}
if (viz[N+N+1] == MAXINT)
return 1;
for (flux = cat[N+N+1], j = N+N+1; viz[j] != -1; j = viz[j])
{
i = viz[j];
cap[i][j] -= flux;
cap[j][i] += flux;
}
return 0;
}
void solve()
{
int i, j;
// creez reteaua de transport
for (i = 1; i <= N; ++i)
for (j = N+1; j <= N+N; ++j)
if (j-N != i)
cap[i][j] = 1;
while (!bfs());
for (i = 1; i <= N; ++i)
for (j = N+1; j <= N+N; ++j)
if (cap[j][i] == 1)
ans++;
}
void write()
{
int i, j;
freopen("harta.out", "w", stdout);
printf("%d\n", ans);
for (i = 1; i <= N; ++i)
for (j = N+1; j <= N+N; ++j)
if (cap[j][i] == 1)
printf("%d %d\n", j-N, i);
}
int main()
{
read();
solve();
write();
return 0;
}