Cod sursa(job #58504)

Utilizator floringh06Florin Ghesu floringh06 Data 6 mai 2007 00:00:23
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#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;
}