Pagini recente » Cod sursa (job #526238) | Cod sursa (job #237312) | Cod sursa (job #574382) | Cod sursa (job #162793) | Cod sursa (job #64367)
Cod sursa(job #64367)
#include <stdio.h>
#include <stdlib.h>
int N, indeg[101], outdeg[101], insum, outsum, flow;
int graph[202][202], queue[202], up[202];
FILE *fin=fopen("harta.in","r"),
*fout=fopen("harta.out","w");
void read()
{
int i;
fscanf(fin,"%d", &N);
for (i = 1; i <= N; i++)
fscanf(fin,"%d %d", &indeg[i], &outdeg[i]),
graph[0][i] = indeg[i], graph[i + N][2 * N + 1] = outdeg[i],
insum += indeg[i], outsum += outdeg[i];
if (insum != outsum) { fprintf(fout,"-1\n"); exit(0); }
}
int augument()
{
int head, tail, i, j;
for (i = 0; i < 2 * N + 2; i++)
queue[i] = 0, up[i] = -1;
queue[0] = 0, up[0] = 0;
for (head = tail = 0; head <= tail; head++)
{
i = queue[head];
for (j = 0; j < 2 * N + 2; j++)
if (graph[i][j] && up[j] == -1)
{
up[j] = i;
queue[++tail] = j;
if (j == 2 * N + 1) { flow++; return 1; }
}
}
return 0;
}
void solve()
{
int i, j;
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (i != j) graph[i][j + N] = 1;
while (augument())
for (i = 2 * N + 1; i; i = up[i])
graph[up[i]][i]--,
graph[i][up[i]]++;
}
void write()
{
int i, j;
if (flow < insum) { fprintf(fout,"-1\n"); return; }
fprintf(fout,"%d\n", flow);
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (graph[j + N][i]) fprintf(fout,"%d %d\n", i, j);
}
int main()
{
read();
solve();
write();
return 0;
}