UVA Online Judge 12125 - March of the Penguin

UVA Online Judge 12125 - March of the Penguins

http://uva.onlinejudge.org/external/121/12125.html
Es un problema clasico de Flujos, en este problema para cada pedazo de hielo es representado por dos nodos, el primero nodo seria el nodo en el que pueden llegar los pinguinos, todas las aristas que llegan a estos nodos, son de capacidad infinita, el segundo nodo son todas las pinguinos que pueden salir, aqui la capacidad tambien es infinita, el truco para evitar que mas de los pinguinos especificados puedan salir del pedazo de hielo es crear una arista entre estos dos nodos que lo representan, con capacidad igual a la que se proporciona en la entrada, al final solo hay que gener un nodo inicial y crear aristas con la capacidad que se especifica en la entrada (esta capacidad es la cantidad de pinguinos que se encuentran en cada pedazo de hielo al inicio ), se ejecuta el algoritmo de flujo maximo poniendo como nodo final cada uno de los nodos incidentes ( Nodos que solo reciben las aristas), y de esta manera si el flujo maximo es igual al total de pinguinos entonces ese nodo es un posible nodo final de reunion de todos los pinguinos.
Para este problema especifico en vez de utilizar una busqueda en amplitud para el flujo utilzo una busqueda en profundidad.
Les dejo el código:

# include "stdio.h"
# include "string.h"


typedef struct { double x, y; int numPenguins, mtime; } PENGUINS;

PENGUINS peng[102];
int graph[204][204], fnet[204][204], vis[204];

double distPenguins( PENGUINS A, PENGUINS B ){
   return (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y); 
}

int min( int a, int b ){ return a < b ? a : b; }

int busquedaEnProfundidad(int currentNode, int destiny, int n, int flow ){
   int r, x;
   if( currentNode == destiny ) return flow;
   if( vis[currentNode] == 1 ) return 0;
   vis[currentNode] = 1;
   for( x = 0; x < n; x++) 
     if( graph[currentNode][x] - fnet[currentNode][x] > 0 ){
      r = busquedaEnProfundidad( x, destiny, n, min(flow, graph[currentNode][x] - fnet[currentNode][x]) );
      if( r > 0 ){
          fnet[currentNode][x] += r;
          fnet[x][currentNode] -= r;
          return r;
      }
     } 
    return 0;
}

int fordFulkerson(int inicio, int destino, int n) {
  memset( fnet, 0, sizeof( fnet ));
  int currentFlow, flow = 0;
  do{
    memset( vis, 0, sizeof( vis ));
    currentFlow = busquedaEnProfundidad( inicio, destino, n, (1<<22));
    flow += currentFlow;
  }while( currentFlow > 0 );
  return flow;
}

main(){
  int cases, ncases, x, y, ini, sumAllPenguins, n, r, cont;
  double dist;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
    scanf("%d %lf", &n, &dist);
    sumAllPenguins = 0;
    for( x = 0; x < n; x++){
      scanf("%lf %lf %d %d", &peng[ x ].x, &peng[ x ].y, &peng[ x ].numPenguins, &peng[x].mtime );
      sumAllPenguins += peng[x].numPenguins;
    }
    memset( graph, 0, sizeof( graph ));
    for( x = 0; x < n; x++)
    for( y = 0; y < n; y++)
      if( x != y && distPenguins( peng[x], peng[y]) <= dist*dist ){
        graph[x*2+1][y*2] = (1<<22);
      }
    for( x = 0; x < n; x++){
       graph[x*2][x*2 + 1] = peng[x].mtime; 
    }
    ini = n*2;
    for( x = 0; x < n; x++)
      graph[ini][ x*2 ] = peng[x].numPenguins;
    cont = 0;
    for( x = 0; x < n; x++){
      r = fordFulkerson( ini, x*2, n * 2 + 3);
      if( r == sumAllPenguins){
       if(cont > 0 ) printf(" ");
       printf("%d", x);
       cont++;
      }
    }
    if( cont == 0 ) printf("-1");
    printf("\n");
  }
  return 0; 
}

Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com