Solución de quimicos, algoritmo de Edmonds (Blossom)

quimicos-edmonds.cpp

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/max_cardinality_matching.hpp>

using namespace std;

// Un grafo no-dirigido.
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> graph;

// Número de parejas de tubos de vidrio.
int N;

// La cantidad de cada sustancia.
int sustancias[64];

// Regresa verdadero si |x| está entre |minimo| y |maximo|.
inline bool dentro_de(int x, const int minimo, const int maximo) {
	return minimo <= x && x <= maximo;
}

// Regresa verdadero si se puede realizar un apareamiento entre las sustancias
// de tal manera que al final todos los tubos de precipitado resultantes
// contengan entre |minimo| y |maximo| ml de sustancia. Un apareamiento normal
// no funciona en este caso, porque no es un grafo bipartito, así que usaremos
// el algoritmo de Edmonds, que nos regresa un conjunto de arcos tal que cada
// nodo tenga a lo más un arco incidente y su cardinalidad es lo más grande
// posible. Al final, si la cardinalidad del conjunto de arcos es igual al
// número de parejas de tubos de vidrio, quiere decir que existe una manera de
// combinarlos. Este algoritmo tiene una complejidad de O(|V|^4).
//
// Más información sobre el algoritmo de Edmonds:
// * http://es.wikipedia.org/wiki/Algoritmo_de_Emparejamiento_de_Edmonds
bool valido(int minimo, int maximo) {
	// Construimos un grafo con 2*N nodos.
	graph g(2 * N);

	// Para cada par de vasos de precipitado,
	for (int i = 0; i < 2 * N; i++) {
		for (int j = 0; j < 2 * N; j++) {
			if (i == j) continue;
			// si ya sea la suma o la diferencia absoluta entre las cantidades de
			// sustancias están dentro del rango válido,
			if (dentro_de(sustancias[i] + sustancias[j], minimo, maximo) ||
			    dentro_de(abs(sustancias[i] - sustancias[j]), minimo, maximo)) {
				// agregamos el arco entre i y j al grafo.
				boost::add_edge(i, j, g);
			}
		}
	}

	// Por último, corremos el algoritmo de Edmonds de apareamiento máximo,
	vector<boost::graph_traits<graph>::vertex_descriptor> mate(2 * N);
	boost::edmonds_maximum_cardinality_matching(g, &mate[0]);

	// y si la cantidad de apareamientos es igual al número de parejas,
	// entonces esa es una solución válida.
	return boost::matching_size(g, &mate[0]) == N;
}

int main() {
	scanf("%d\n", &N);

	for (int i = 0; i < 2 * N; i++) {
		scanf("%d\n", &sustancias[i]);
	}

	sort(sustancias, sustancias + 2 * N);

	const int minimo = 0;
	const int maximo = sustancias[2 * N - 2] + sustancias[2 * N - 1];

	// Hacemos búsqueda binaria sobre el ancho del intervalo en el cual puede
	// estar la solución. Para cada ancho, vamos a tratar de ver si es posible
	// hacer un apareamiento entre tubos de vidrio de tal manera que después de
	// combinar los tubos de cada pareja, todos terminen con entre |base| y
	// |base| + |ancho| ml de solución.
	int a = 0, b = maximo;
	while (a < b) {
		int ancho = (a + b) / 2;
		bool posible = false;
		// Para un |ancho| dado, vamos a intentar con todos los valores posibles que
		// estén entre |minimo| y |maximo|.
		for (int base = minimo; base <= maximo - ancho; base++) {
			if (valido(base, base + ancho)) {
				posible = true;
				break;
			}
		}
		if (posible) {
			b = ancho;
		} else {
			a = ancho + 1;
		}
	}

	printf("%d\n", b);
}